Description

Given two strings $A$ and $B$, representing the names of two of JYY's friends. Let $A(i,\,j)$ denote the substring of $A$ formed by the $i$-th letter through the $j$-th letter. Similarly, we define $B(x,\,y)$.

JYY found that the closeness of the relationship between two friends is equal to the number of quadruples $(i,\,j,\,x,\,y)$ that satisfy all of the following conditions:

1. $1\leq i\leq j\leq |A|$.
2. $1\leq x\leq y\leq |B|$.
3. $A(i,\,j)=B(x,\,y)$.
4. $A(i,\,j)$ is a palindrome string.

Here, $|A|$ denotes the length of string $A$.

JYY hopes you can help him compute the closeness of the relationship between these two friends.

Input Format

The input consists of two lines, each containing a string $A$ and $B$ made up of uppercase letters.

Output Format

Output one line containing one integer, representing the closeness, i.e., the number of valid quadruples.

PUPPY
PUPPUP

17

Hint

Constraints: $1\leq |A|,\,|B|\leq 50000$.

Translated by ChatGPT 5