Substring and Subsequence

题意翻译

有两个非空字符串 $s,t$,都**仅有小写字母**构成。 令 $x$ 为 $s$ 的**非空子串**, $y$ 为 $s$ 的**非空子序列**,问有多少种方式,使 $x$ 与 $y$ 相同。 两种方式 $(x_1,y_1),(x_2,y_2)$ 不同当且仅当 $x_1 \neq x_2$ 或 $y_1 \neq y_2$。 令 $\begin{aligned}&x_1 = s[a_1......b_1]=s_{a_1}s_{a_1+1}...s_{b_1}\\&x_2 =s[a_2......b_2]=s_{a_2}s_{a_2+1}...s_{b_2}\\&y_1=s[p_1p_2......p_{|y_1|}]=s_{p_1}s_{p_2}......s_{p_{|y1|}}\\&y_2=s[q_1q_2......q_{|y_2|}]=q_{p_1}q_{p_2}......q_{p_{|y1|}}\end{aligned}$ $x_1\neq x_2$ 时, $a_1\neq a_2$ 或 $b_1 \neq b_2$。 $y_1 \neq y_2$ 时, $p \neq q$。 $\texttt{Translated by fjy666}$

题目描述

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_{1}s_{2}...\ s_{|s|} $ . A substring of $ s $ is a non-empty string $ x=s[a...\ b]=s_{a}s_{a+1}...\ s_{b} $ ( $ 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_{1}p_{2}...\ p_{|y|}]=s_{p1}s_{p2}...\ s_{p|y|} $ ( $ 1<=p_{1}&lt;p_{2}&lt;...&lt;p_{|y|}<=|s| $ ). For example, "coders" is a subsequence of "codeforces". Two subsequences $ u=s[p_{1}p_{2}...\ p_{|u|}] $ and $ v=s[q_{1}q_{2}...\ q_{|v|}] $ 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.

输出格式


Print a single number — the number of different pairs " $ x $ $ y $ " 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. As the answer can be rather large, print it modulo $ 1000000007 $ $ (10^{9}+7) $ .

输入输出样例

输入样例 #1

aa
aa

输出样例 #1

5

输入样例 #2

codeforces
forceofcode

输出样例 #2

60

说明

Let's write down all pairs " $ x $ $ y $ " that form the answer in the first sample: " $ s[1...1] $ $ t[1] $ ", " $ s[2...2] $ $ t[1] $ ", " $ s[1...1] $ $ t[2] $ "," $ s[2...2] $ $ t[2] $ ", " $ s[1...2] $ $ t[1 2] $ ".