Bài toán Dãy con chung dài nhất (LCS) là một trong những khối kiến thức nền tảng và cổ điển bậc nhất của Khoa học Máy tính. Xuất hiện từ những năm 1970 trong các công trình nghiên cứu về so sánh chuỗi gen DNA, giải mã trình tự sinh học và công cụ so sánh tệp tin huyền thoại diff trên hệ điều hành Unix, LCS đã mở ra kỷ nguyên phát triển rực rỡ cho kỹ thuật Quy hoạch động.

Trong phân tích cú pháp và xử lý chuỗi nâng cao, việc chỉ xác định độ dài của dãy con chung dài nhất đôi khi là chưa đủ. Một bài toán hóc húa hơn đặt ra là phải đếm số lượng các dãy con chung dài nhất phân biệt giữa hai chuỗi ký tự. Hai dãy con được xem là phân biệt nếu chúng có nội dung chuỗi khác nhau, bất kể chúng được trích xuất từ các vị trí chỉ số nào trong hai chuỗi ban đầu.

• Dãy con: Thu được bằng cách xóa đi một số ký tự mà không làm thay đổi thứ tự tương quan của các ký tự còn lại.
• Độ dài cực đại: Dãy con chung phải đạt độ dài lớn nhất có thể giữa hai chuỗi ~A~ và ~B~.
• Tính phân biệt: Hai dãy con có cùng nội dung chuỗi nhưng xuất hiện từ các vị trí chỉ số khác nhau chỉ được tính là ~1~ dãy duy nhất.
• Chia lấy dư: Do số lượng dãy con có thể rất lớn, kết quả cần được chia lấy dư cho ~10^9 + 7~.

Trong bài tập này, bạn được cấp hai chuỗi ký tự ~A~ và ~B~. Hãy viết chương trình đếm số lượng dãy con chung dài nhất phân biệt của hai chuỗi này!

Input

• Dòng ~1~: Chuỗi ký tự ~A~.
• Dòng ~2~: Chuỗi ký tự ~B~.
• Lưu ý: ~1 \le |A|, |B| \le 2000~, các chuỗi chỉ gồm các chữ cái in thường tiếng Anh (a - z).

Output

• In ra một dòng duy nhất chứa một số nguyên: Số lượng dãy con chung dài nhất phân biệt của ~A~ và ~B~ sau khi chia lấy dư cho ~10^9 + 7~.

Example Input 1

aaa
aa

Example Output 1

1

Example Input 2

ab
ba

Example Output 2

2

Example Input 3

aba
bab

Example Output 3

2