在学习了一些关于回文的奇特算法后,Couti 发现回文非常有趣,所以他想用这个问题来挑战你。
Couti 有两个字符串 $$$A$$$ 和 $$$B$$$。因为他喜欢回文,所以他想选择 $$$a$$$ 作为 $$$A$$$ 的一些非空回文子串,并选择 $$$b$$$ 作为 $$$B$$$ 的一些非空回文子串。将它们连接起来,他将得到字符串$$$ab$$$。
Couti 认为他可以通过这种方式获得的字符串很有趣,因此他想知道他可以获得多少种不同的字符串。
输入
第一行包含单个字符串 $$$A$$$ ($$$1 \le |A| \le 2 \cdot 10^5$$$)。
第二行包含单个字符串 $$$B$$$ ($$$1 \le |B| \le 2 \cdot 10^5$$$)。
字符串 $$$A$$$ 和 $$$B$$$ 仅包含小写英文字母。
输出
第一行也是唯一一行应包含一个整数 - 可能的字符串数量。
示例
输入 #1
aa aba
输出 #1
6
输入 #2
aaba abaa
输出 #2
15
注意
在第一个示例中,可获得的字符串是
- “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”只会计算一次。