問題文

かつて、Common Palindromesという、その名の通り$2$個の文字列の共通部分回文のペアの個数を求める問題があった。この問題は当時の参加者たちを大いに苦しめた。 あれから$3$年以上の月日が流れ、CPUの性能も競技プログラマの質も格段に向上した。 Common Palindromesでの最速実行時間は$0.05$秒を切るという。したがって文字列の長さを$10$倍にしてもきっと解けるはずだ。

$2$個の文字列$S, T$が与えられるので、以下の条件をすべて満たす組$(i,j,k,l)$の個数を求めよ。なお、文字列$U$の$x$文字目以降$y$文字目以前の連続部分文字列を$U[x,y]$で表す。

• $1\le i\le j\le (Sの長さ).$
• $1\le k\le l\le (Tの長さ).$
• $S[i,j]=T[k,l].$
• $S[i,j]$は回文。

入力

$S$
$T$

• $1\le (Sの長さ)\le 500000$
• $1\le (Tの長さ)\le 500000$
• $S, T$は英大文字('A'-'Z')のみからなる
• 上記の制約から、答えはつねに$10^{18}$以下であることが保証される。
• ※この問題は原題の公開コードをコピペしてACされないように制約が若干きつめに設定されています!!

出力

組$(i,j,k,l)$の個数を出力してください。 最後に改行してください。

サンプル

AABA
BAAB

9

USAGI
MYON

0