Background

JYY has many, many good friends in JSOI, such as PUPPY, KFC, and PUPPUP. With so many friends, JYY is happy every day. One day, JYY found that how well friends get along is closely related to their names. For example, PUPPY and PUPPUP get along especially well, but their relationship with KFC is just average. After thinking hard for a long time, JYY finally discovered the pattern. Now JYY wants to know how close the relationship is between two friends. Can you help JYY?

Problem 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