Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Aliens

By itissabbir · Limits 1s, 512 MB

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

InputOutput
ad
d
1
InputOutput
abcab
cba
4

Discussion

Statistics


100% Solution Ratio

YouKnowWhoEarliest, 4w ago

YouKnowWhoFastest, 0.1s

YouKnowWhoLightest, 28 MB

YouKnowWhoShortest, 1114B

Submit

Login to submit

Related Contests

SEC Intra Campus Programming Contest, CSE Fest 2020 Ended at 2020-02-19 11:02:00 +0000 UTC