19 February 2020, Unidentified flying object (UFO) has captured student’s attention on top of the CSE building of Sylhet Engineering College. The door of the UFO was closed. Students found a tiny LCD monitor on the door. It’s just displaying 2 strings on separate lines. Let's call the strings p and q. Actually the passcode of the door is hidden in these two strings and length is minimal. The passcode is any string if and only if p and q are its subsequence.
Example - let p = abcab & q = cba
Accepted Passcodes of the door are -abcaba, abcbab, acbcab, cabcab.
Note: string s =abcabcba is not an acceptable passcode although both p and q are subsequence of s because the length is not minimal.
Find the number of acceptable passcodes modulo 109 + 7
Input
The input consists of 2 lines, each of them containing string p and q (lowercase English letters). The length of each string doesn't exceed 2000 characters.
Output
Output the number of passcodes of minimal length modulo 109 + 7.
Samples
| Input | Output |
|---|---|
ad d | 1 |
| Input | Output |
|---|---|
abcab cba | 4 |
