Problem Statement

Once upon a time, there was a problem called Common Palindromes, which, as its name suggests, asked for the number of pairs of common palindromic substrings of $2$ strings. This problem caused the contestants of the time a great deal of suffering. More than $3$ years have passed since then, and both CPU performance and the quality of competitive programmers have improved dramatically. The fastest execution time for Common Palindromes is said to be under $0.05$ seconds. Therefore, it should surely still be solvable even if the string lengths are multiplied by $10$.

Given $2$ strings $S, T$, find the number of tuples $(i,j,k,l)$ satisfying all of the following conditions. Here, $U[x,y]$ denotes the contiguous substring of a string $U$ from the $x$-th character through the $y$-th character.

• $1\le i\le j\le (Sの長さ).$
• $1\le k\le l\le (Tの長さ).$
• $S[i,j]=T[k,l].$
• $S[i,j]$ is a palindrome.

Input

$S$
$T$

• $1\le (Sの長さ)\le 500000$
• $1\le (Tの長さ)\le 500000$
• $S, T$ consist only of uppercase English letters ('A'-'Z')
• From the above constraints, the answer is guaranteed to always be at most $10^{18}$.
• * The constraints of this problem are set slightly tight so that copying and pasting published code for the original problem will not get AC!!

Output

Output the number of tuples $(i,j,k,l)$. Print a newline at the end.

Sample

AABA
BAAB

9

USAGI
MYON

0