CF163A.Substring and Subsequence

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__p_1_s__p_2... s__p|y| (1 ≤ _p_1 < _p_2 < ... < 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.

一天，Polycarpus 得到了两个非空字符串 $s$ 和 $t$，均由小写拉丁字母组成。Polycarpus 对字符串非常熟悉，因此他立刻想到：满足如下条件的不同数对 $(x, y)$ 共有多少个？其中 $x$ 是字符串 $s$ 的一个子串，$y$ 是字符串 $t$ 的一个子序列，且 $x$ 与 $y$ 的内容完全相同。若两个数对所含的 $s$ 的子串不同，或所含的 $t$ 的子序列不同，则认为这两个数对不同。请通读整个题面以准确理解“不同子串”和“不同子序列”的定义。

字符串 $s$ 的长度即为其所含字符的个数。若记字符串 $s$ 的长度为 $|s|$，则可将该字符串表示为 $s = s_1 s_2 \dots s_{|s|}$。

$s$ 的一个子串是指一个非空字符串 $x = s[a\ldots b] = s_a s_{a+1} \dots s_b$，其中 $1 \le a \le b \le |s|$。例如，“code”和“force”都是“codeforces”的子串，而“coders”则不是。“codeforces”中，子串 $s[2\ldots2]$ 与 $s[6\ldots6]$ 被视为不同的子串（尽管它们的内容相同），因为当且仅当 $a \ne c$ 或 $b \ne d$ 时，子串 $s[a\ldots b]$ 与 $s[c\ldots d]$ 被认为是不同的。

$s$ 的一个子序列是指一个非空字符串 $y = s[p_1 p_2 \dots p_{|y|}] = s_{p_1} s_{p_2} \dots s_{p_{|y|}}$，其中 $1 \le p_1 < p_2 < \dots < p_{|y|} \le |s|$。例如，“coders”是“codeforces”的一个子序列。对于两个子序列 $u = s[p_1 p_2 \dots p_{|u|}]$ 和 $v = s[q_1 q_2 \dots q_{|v|}]$，若下标序列 $p$ 与 $q$ 不同，则认为 $u$ 与 $v$ 是不同的子序列。

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.

输入包含两行。第一行包含字符串 $s$（$1 \leq |s| \leq 5000$），第二行包含字符串 $t$（$1 \leq |t| \leq 5000$）。两个字符串均由小写拉丁字母组成。

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 (109 + 7).

输出一个整数——满足以下条件的不同数对 “x y” 的个数：x 是字符串 s 的子串，y 是字符串 t 的子序列，且 x 与 y 的内容相同。由于答案可能非常大，请将结果对 1000000007（即 $10^9 + 7$）取模后输出。

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]".

我们写出第一个样例中构成答案的所有数对“x y”：“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]”。