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*_{p1}*s*_{p2}... *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.

提交代码