#P1081H. Palindromic Magic

    ID: 4504 Type: RemoteJudge 2000ms 1024MiB Tried: 0 Accepted: 0 Difficulty: (None) Uploaded By: Tags>data structureshashingstrings*3500

Palindromic Magic

No submission language available for this problem.

Description

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.

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.

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

Input

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.

Output

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

Samples

aa
aba

6

aaba
abaa

15

Note

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.