You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

出题人

小津

小津的字符串

字符串 A = a1a2...an 的长度为 n，记作 |A|=n。同样，两个字符串 A = a1a2...an 和 B = b1b2...bm 的连接表示为 a1a2...anb1b2...bm，记作 A + B。

两个长度相同的字符串 A = a1a2...an 和 B = b1b2...bn 之间的编辑距离是满足 ai ≠ bi 的索引 i 的数量。

如果字符串 A 是由另一个字符串 B 的前 k 个字符组成的（k ≤ |B|），则称 A 为 B 的第 k 个前缀。如果字符串 P 的长度不超过 Q，并且 P 与 Q 的 |P| 长度前缀之间的编辑距离最多为 1，则称 P 为 Q 的一个几乎前缀。

给定两个由小写英文字母组成的字符串 S 和 T，要求找出所有将 S 分割成若干部分的方式，使得每一部分都是字符串 T 的非空几乎前缀，然后报告所有方式中各部分数量平方和的模 998244353。更正式地，如果 S = P1 + P2 + ... + Pn 是一种可能的分割方式，需要计算：

输入

• 第一行包含一个字符串 S（1 ≤ |S| ≤ 1,000,000），由小写英文字母组成。
• 第二行包含一个字符串 T（1 ≤ |T| ≤ 1,000,000），由小写英文字母组成。

输出

• 输出一个整数：所有分割方式中各部分数量平方和的模 998244353。

样例

样例输入1

ababaab
aba

样例输出1

473

样例输入2

ac
ccpc

样例输出2

5

注意

在第一个示例中（S = ababaab, T = aba），有 19 种分割方式：

• 1 种 3 部分的方式，即 ab + aba + ab；
• 6 种 4 部分的方式，例如 a + b + aba + ab；
• 7 种 5 部分的方式，例如 a + b + ab + a + ab；
• 4 种 6 部分的方式，例如 a + b + a + b + a + ab；
• 1 种 7 部分的方式，即 a + b + a + b + a + a + b。

因此，第一个示例的结果为 (3^2 + 6 × 4^2 + 7 × 5^2 + 4 × 6^2 + 7^2) mod 998244353 = 473。