CF1081H.Palindromic Magic

After learning some fancy algorithms about palindromes, Chouti found palindromes very interesting, so he wants to challenge you with this problem.

Chouti has got two strings $A$ and $B$. Since he likes palindromes, he would like to pick $a$ as some non-empty palindromic substring of $A$ and $b$ as some non-empty palindromic substring of $B$. Concatenating them, he will get string $ab$.

Chouti thinks strings he could get this way are interesting, so he wants to know how many different strings he can get.

学习了一些关于回文的精妙算法后，Chouti 觉得回文非常有趣，因此他想用这道题来挑战你。

Chouti 有两个字符串 $A$ 和 $B$。由于他喜欢回文，他希望选取 $a$ 为 $A$ 的某个非空回文子串，$b$ 为 $B$ 的某个非空回文子串，并将它们连接起来，得到字符串 $ab$。

Chouti 认为通过这种方式能得到的字符串很有趣，因此他想知道：他一共能构造出多少个不同的字符串？

The first line contains a single string $A$ ($1 \le |A| \le 2 \cdot 10^5$).

The second line contains a single string $B$ ($1 \le |B| \le 2 \cdot 10^5$).

Strings $A$ and $B$ contain only lowercase English letters.

第一行包含一个字符串 $A$（$1 \le |A| \le 2 \cdot 10^5$）。

第二行包含一个字符串 $B$（$1 \le |B| \le 2 \cdot 10^5$）。

字符串 $A$ 和 $B$ 仅由小写英文字母组成。

The first and only line should contain a single integer — the number of possible strings.

第一行且仅一行应包含一个整数——可能的字符串数量。

In the first example, attainable strings are

• "a" + "a" = "aa",
• "aa" + "a" = "aaa",
• "aa" + "aba" = "aaaba",
• "aa" + "b" = "aab",
• "a" + "aba" = "aaba",
• "a" + "b" = "ab".

In the second example, attainable strings are "aa", "aaa", "aaaa", "aaaba", "aab", "aaba", "ab", "abaa", "abaaa", "abaaba", "abab", "ba", "baa", "baba", "bb".

Notice that though "a"+"aa"="aa"+"a"="aaa", "aaa" will only be counted once.

在第一个例子中，可生成的字符串有：

• "a" + "a" = "aa",
• "aa" + "a" = "aaa",
• "aa" + "aba" = "aaaba",
• "aa" + "b" = "aab",
• "a" + "aba" = "aaba",
• "a" + "b" = "ab".

在第二个例子中，可生成的字符串有 "aa"、"aaa"、"aaaa"、"aaaba"、"aab"、"aaba"、"ab"、"abaa"、"abaaa"、"abaaba"、"abab"、"ba"、"baa"、"baba"、"bb"。

注意：尽管 "a"+"aa"="aa"+"a"="aaa"，但 "aaa" 仅被计数一次。