题目描述

给定两个字符串 $s$ 和 $t$，统计满足以下所有条件的元组 $(i, j, k)$ 的个数：

1. $1 \le i \le j \le |s|$
2. $1 \le k \le |t|$
3. $j - i + 1 > k$
4. 将 $s$ 的第 $i$ 个字符到第 $j$ 个字符，与 $t$ 的第 $1$ 个字符到第 $k$ 个字符拼接起来，得到的字符串是一个回文串。

回文串是指正读和反读都相同的字符串，例如 "$\texttt{abcba}$" 或 "$\texttt{xyzzyx}$"。

输入格式

第一行是字符串 $s$（$2 \le |s| \le 10^6$）。

第二行是字符串 $t$（$1 \le |t| < |s|$）。

$s$ 和 $t$ 均仅包含小写拉丁字母。

输出格式

输出一个整数，表示满足条件的元组个数。

ababa
aba

5

aabbaa
aabb

7

提示

翻译由 DeepSeek V4 Pro 完成