(Đề đề xuất DHBB 2017 của THPT CHUYÊN HÙNG VƯƠNG PHÚ THỌ)

Cho hai xâu ký tự ~s~ và ~p~ 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 ~s~ và một số ký tự của xâu ~p~ để 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.

Input

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

Giới hạn:

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

Output

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

Sample

Input #1

abc
aaa

Output #1

3

Hint

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

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

Problem source: Chuyên Sơn La Online Judge