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₁s₂... s_|s|.

A substring of s is a non-empty string x = s[a... b] = s_as_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₁p₂... p_|y|] = s_p1s_p2... s_p|y| (1 ≤ p₁ < p₂ < ... < p_|y| ≤ |s|). For example, "coders" is a subsequence of "codeforces". Two subsequences u = s[p₁p₂... p_|u|] and v = s[q₁q₂... q_|v|] are considered different if the sequences p and q are different.