给定两个字符串 $$$x$$$ 和 $$$y$$$,两者均仅包含小写拉丁字母。令 $$$|s|$$$ 为字符串 $$$s$$$ 的长度。
如果序列 $$$a$$$ 恰好由 $$$|x|$$$ 0 和 $$$|y|$$$ 1 以某种顺序组成,那么我们将其称为合并序列。
合并 $$$z$$$ 是根据以下规则从序列 $$$a$$$ 生成的:
- 如果 $$$a_i=0$$$,则从 $$$x$$$ 的开头删除一个字母并将其附加到 $$$z$$$ 的末尾;
- 如果 $$$a_i=1$$$,则从 $$$y$$$ 开头删除一个字母并将其附加到 $$$z$$$ 末尾。
如果存在某个位置 $$$i$$$ 使得 $$$a_i \neq b_i$$$ ,则两个合并序列 $$$a$$$ 和 $$$b$$$ 是不同的。
如果对于从 $$$2$$$ 到 $$$|z|$$$ $$$z_{i-1} \neq z_i$$$ 的所有 $$$i$$$,我们称字符串 $$$z$$$ 为混沌。
设 $$$s[l,r]$$$ 对于某些 $$$1 \le l \le r \le |s|$$$ 是 $$$s$$$ 的连续字母的子串,从位置 $$$l$$$ 开始,到位置 $$$r$$$ 结束(含)。
令 $$$f(l_1, r_1, l_2, r_2)$$$ 为 $$$x[l_1,r_1]$$$ 和 $$$y[l_2,r_2]$$$ 产生混沌合并的不同合并序列的数量。请注意,仅考虑 $$$x$$$ 和 $$$y$$$ 的非空子字符串。
计算$$$\sum \limits_{1 \le l_1 \le r_1 \le |x| \\ 1 \le l_2 \le r_2 \le |y|} f(l_1, r_1, l_2, r_2)$$$。输出对 $$$998\,244\,353$$$ 取模的答案。
输入
第一行包含字符串 $$$x$$$ ($$$1 \le |x| \le 1000$$$)。
第二行包含字符串 $$$y$$$ ($$$1 \le |y| \le 1000$$$)。
两个字符串均仅包含小写拉丁字母。
输出
打印单个整数 - $$$f(l_1, r_1, l_2, r_2)$$$ 与 $$$1 \le l_1 \le r_1 \le |x|$$$ 和 $$$1 \le l_2 \le r_2 \le |y|$$$ 模 $$$998\,244\,353$$$ 的总和。
示例
输入 #1
aaa bb
输出 #1
24
输入 #2
code forces
输出 #2
1574
输入 #3
aaaaa aaa
输出 #3
0
输入#4
justamassivetesttocheck howwellyouhandlemodulooperations
输出#4
667387032
注意
在第一个示例中有:
- $$$6$$$子字符串“a”和“b”对,每个子字符串都有有效的合并序列“01”和“10”;
- $$$3$$$子字符串“a”和“bb”对,每个子字符串都有一个有效的合并序列“101”;
- $$$4$$$子串“aa”和“b”对,每个子串都有一个有效的合并序列“010”;
- $$$2$$$子字符串“aa”和“bb”对,每个子字符串都有有效的合并序列“0101”和“1010”;
- $$$2$$$ 子字符串“aaa”和“b”对,每个都没有有效的合并序列;
- $$$1$$$ 子字符串“aaa”和“bb”对,具有有效的合并序列“01010”;
因此,答案是 $$$6 \cdot 2 + 3 \cdot 1 + 4 \cdot 1 + 2 \cdot 2 + 2 \cdot 0 + 1 \cdot 1 = 24$$$。