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. 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) . Let's write down all pairs " x y " that form the answer in the first sample: " s 1...1 t