One day Polycarpus got hold of two non-empty strings *s* and *t*, consisting of lowercase Latin letters. Polycarpus is quite good with strings, so he immediately wondered, how many different pairs of "*x* *y*" are there, such that *x* is a substring of string *s*, *y* is a subsequence of string *t*, and the content of *x* and *y* is the same. Two pairs are considered different, if they contain different substrings of string *s* or different subsequences of string *t*. Read the whole statement to understand the definition of different substrings and subsequences.

The length of string *s* is the number of characters in it. If we denote the length of the string *s* as |*s*|, we can write the string as *s* = *s*<sub class="lower-index">1</sub>*s*<sub class="lower-index">2</sub>... *s*<sub class="lower-index">|*s*|</sub>.

A substring of *s* is a non-empty string *x* = *s*[*a*... *b*] = *s*<sub class="lower-index">*a*</sub>*s*<sub class="lower-index">*a* + 1</sub>... *s*<sub class="lower-index">*b*</sub> (1 ≤ *a* ≤ *b* ≤ |*s*|). For example, "code" and "force" are substrings or "codeforces", while "coders" is not. Two substrings *s*[*a*... *b*] and *s*[*c*... *d*] are considered to be different if *a* ≠ *c* or *b* ≠ *d*. For example, if *s*="codeforces", *s*[2...2] and *s*[6...6] are different, though their content is the same.

A subsequence of *s* is a non-empty string *y* = *s*[*p*<sub class="lower-index">1</sub>*p*<sub class="lower-index">2</sub>... *p*<sub class="lower-index">|*y*|</sub>] = *s*<sub class="lower-index">*p*<sub class="lower-index">1</sub></sub>*s*<sub class="lower-index">*p*<sub class="lower-index">2</sub></sub>... *s*<sub class="lower-index">*p*<sub class="lower-index">|*y*|</sub></sub> (1 ≤ *p*<sub class="lower-index">1</sub> &lt; *p*<sub class="lower-index">2</sub> &lt; ... &lt; *p*<sub class="lower-index">|*y*|</sub> ≤ |*s*|). For example, "coders" is a subsequence of "codeforces". Two subsequences *u* = *s*[*p*<sub class="lower-index">1</sub>*p*<sub class="lower-index">2</sub>... *p*<sub class="lower-index">|*u*|</sub>] and *v* = *s*[*q*<sub class="lower-index">1</sub>*q*<sub class="lower-index">2</sub>... *q*<sub class="lower-index">|*v*|</sub>] are considered different if the sequences *p* and *q* are different.
The input consists of two lines. The first of them contains *s* (1 ≤ |*s*| ≤ 5000), and the second one contains *t* (1 ≤ |*t*| ≤ 5000). Both strings consist of lowercase Latin letters.
aa
aa
5
codeforces
forceofcode
60
coderscontest
codeforces
39
a
b
0
ab
bbbba
5
abbbccbba
abcabc
33
zxzxzxzxzxzxzx
d
0
pfdempfohomnpgbeegikfmflnalbbajpnpgeacaicoehopgnabnklheepnlnflohjegcciflmfjhachnhekckfjgoffhkblncidn
idlhklpclcghngeggpjdgefccihndpoikojdjnbkdfjgaanoolfmnifnmbpeeghpicehjdiipnlfnjpglidpnnnjfmjfhbcogojkcfflmmfcgajbjbfaikhmjofbnjnaolbcdkelcieeodbfjcfiblhhmeelmpcmmcdhjcnnfklgedjjbaljndjonanlojclboeelkab
26774278
sbypoaavsbqxfiqvpbjyimhzotlxuramhdamvyobsgaehwhtfdvgvlxpophtvzrmvyxwyzeauyatzitsqvlabufbcefaivwzoccfvhrdbzlmzoofczqzbxoqioctzzxqksuorhnldrfavlhyfyobvnqsyegsbvlusxchixbddzbwwnvuulcarguxvnvzkdqcjxxdetll
lbawrainjjdgkdmwkqzxlwxhzjyrxbuwjhnvjlnmgfyrxdynsanvibfhngsioisbyldaplituqhebeicpsyerpiiqpjtnxvuotjv
8095
ababbabbab
ababb
75
bbabb
bababbbbab
222
ababababab
ababb
74
b
ab
1
ab
a
1
xzzxxxzxzzzxzzzxxzzxzzxzxzxxzxxzxxzxzzxxzxxzxxxzxzxzxxzzxxxxzxzzzxxxzxzxxxzzxxzxxzxxzzxxzxxzxzxzzzxzzzzxzxxzzxzxxzxxzzxzxzx
zzx
291
zxx
xzzxxxxzzzxxxzzxxxzxxxzzxxzxxxzzxzxxzxxzxxzxzxxzxxxxzzxxzzxzzxxzzxxzxzxzxxzxzxzxxxzxxzzxxzxxxxzzxxxzxxxzxzxzzxzzxxxxzzxxzxz
46917
s,t,dp=input(),input(),[]
for i in range(5001):
    dp.append([])
    for j in range(5001):
        dp[i].append(0)
for i in range(len(s)):
    for j in range(len(t)):
        if s[i]==t[j]:
            dp[i+1][j+1]=(dp[i][j]+1+dp[i+1][j])%1000000007
        else:
            dp[i+1][j+1]=dp[i+1][j]%1000000007
ans=0
for i in range(len(s)): ans+=dp[i+1][len(t)]%1000000007
print(ans)
