D. DPSUBSTR3 – Xâu con giống nhau

Cho hai xâu ký tự và chỉ chứa các ký tự la tinh thường. Hãy đếm số cách xóa đi một số ký tự của xâu và một số ký tự của xâu để hai xâu nhận được là khác rỗng và giống nhau (kể cả trường hợp không xóa ký tự nào). Hai cách được xem là khác nhau nếu tồn tại ít nhất một vị trí bị xóa của một trong hai xâu là khác nhau. Do số cách xóa có thể rất lớn nên ta chỉ lấy phần dư khi chia cho 1000000007.

Dữ liệu vào:

• Dòng đầu chứa xâu ;
• Dòng hai chứa xâu .

Dữ liệu ra:

• Một số nguyên duy nhất là phần dư của số cách xóa khi chia cho 1000000007.

Ví dụ:

Dữ liệu vào:

abc
aaa

Dữ liệu ra:

3

Giải thích:

Các cách xóa như sau:

• Cách : Xóa hai ký tự bc ở xâu , xóa hai ký tự aa cuối ở xâu
• Cách : Xóa hai ký tự bc ở xâu , xóa hai ký tự aa đầu ở xâu
• Cách : Xóa hai ký tự bc ở xâu , xóa ký tự đầu và ký tự cuối ở xâu

Giới hạn:

• Các xâu khác rỗng và có độ dài không quá ký tự.