Given two strings, find the number of ways to choose one substring from each string such that the two substrings are identical. Two ways are considered different if and only if the substrings differ in at least one position (i.e., they have different starting or ending positions in their respective strings).
Input
Two lines, each containing a string $s1$ and $s2$, with lengths $n1$ and $n2$ respectively.
Output
Output an integer representing the answer.
Constraints
- For 20% of the data, $1 \le n1, n2 \le 500$.
- For 40% of the data, $1 \le n1, n2 \le 5000$.
- For 100% of the data, $1 \le n1, n2 \le 200000$, and the strings consist only of lowercase letters.
Examples
Input 1
aabb bbaa
Output 1
10