Migrated from Lutece 3279 Another Day of Sun

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Tags: 回文自动机，字符串 Hash

在一个阳光灿烂的早晨，你站在洛杉矶的高速公路上，汽车喇叭声不绝于耳，人们在等待着另一个美好的日子的开始。你的任务是找到一些特别的回文子串，它们在两个不同的字符串中相遇，像是命运般的交织。

给定两个字符串 $S_1$ 和 $S_2$，你需要找到满足以下条件的子串对数：

1. 子串分别来自字符串 $S_1$ 和 $S_2$。
2. 这两个子串相等。
3. 这两个子串都是回文串。

回文串是指一个字符串从前往后读和从后往前读都相同。

Input

第一行一个仅包含大写字母的字符串表示 $S_1$

第二行一个仅包含大写字母的字符串表示 $S_2$

Output

输出一个整数，表示满足条件的子串对数

Samples

ABABA
BABAB

16

Constraints

$|S_1|,|S_2|\leq 2\times 10^5$

Resources

2024 UESTC ICPC Training for String