(Đề đề xuất DHBB 2017 của THPT CHUYÊN HÙNG VƯƠNG PHÚ THỌ)
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