Xâu con của một xâu là xâu đó khi xóa đi một vài ký tự và giữ nguyên thứ tự các ký tự còn lại. Ví dụ, ac, ad, acd là các xâu con của abcd.

Bạn được cho hai xâu \(s\) và \(t\). Nhiệm vụ của bạn là xét tất cả các xâu con khác rỗng của \(s\) và các xâu con khác rỗng của \(t\), đếm xem có bao nhiêu cặp xâu bằng nhau. Vì kết quả rất lớn nên chỉ cần in ra phần dư của kết quả sau khi chia cho \(10^9 + 7\).

Input

• Dòng đầu tiên gồm xâu \(s\) có độ dài không quá \(10^4\).
• Dòng tiếp theo gồm xâu \(t\) có độ dài không quá \(10^4\).
• Dữ liệu đảm bảo cả hai xâu chỉ gồm các ký tự in thường từ a đến z.

Output

• Một dòng duy nhất gồm phần dư của số cặp xâu bằng nhau khi chia cho \(10^9 + 7\).

Example

aba
abc

4

abc
bac

5

Scoring

• \(10\%\) số điểm có độ dài xâu \(s\) là \(1\).
• \(10\%\) số điểm khác có độ dài xâu \(s\) là \(2\).
• \(8\%\) số điểm khác có độ dài hai xâu không quá \(10\).
• \(8\%\) số điểm khác có độ dài hai xâu không quá \(15\).
• \(8\%\) số điểm khác có độ dài hai xâu không quá \(20\).
• \(8\%\) số điểm khác có xâu \(s\) chỉ gồm một loại ký tự và có độ dài không quá \(7000\).
• \(8\%\) số điểm khác có độ dài hai xâu không quá \(100\).
• \(8\%\) số điểm khác có độ dài hai xâu không quá \(300\).
• \(8\%\) số điểm khác có độ dài hai xâu không quá \(2000\).
• \(8\%\) số điểm khác có độ dài hai xâu không quá \(5000\).
• \(8\%\) số điểm khác có độ dài hai xâu không quá \(7000\).
• \(8\%\) số điểm còn lại không có giới hạn gì thêm.