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.