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=s1s2... s|s|.

A substring of s is a non-empty string x=s[a... b]=sasa+1... sb (1 \le a \le b \le |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 \neq c or b \neq 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[p1p2... p|y|]=sp1sp2... sp|y| (1 \le p1 \lt p2 \lt ... \lt p|y| \le |s|). For example, "coders" is a subsequence of "codeforces". Two subsequences u=s[p1p2... p|u|] and v=s[q1q2... 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 \le |s| \le 5000), and the second one contains t (1 \le |t| \le 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 (109+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[12]".