CF1499E.Chaotic Merge

You are given two strings $x$ and $y$, both consist only of lowercase Latin letters. Let $|s|$ be the length of string $s$.

Let's call a sequence $a$ a merging sequence if it consists of exactly $|x|$ zeros and exactly $|y|$ ones in some order.

A merge $z$ is produced from a sequence $a$ by the following rules:

• if $a_i=0$, then remove a letter from the beginning of $x$ and append it to the end of $z$;
• if $a_i=1$, then remove a letter from the beginning of $y$ and append it to the end of $z$.

Two merging sequences $a$ and $b$ are different if there is some position $i$ such that $a_i \neq b_i$.

Let's call a string $z$ chaotic if for all $i$ from $2$ to $|z|$ $z_{i-1} \neq z_i$.

Let $s[l,r]$ for some $1 \le l \le r \le |s|$ be a substring of consecutive letters of $s$, starting from position $l$ and ending at position $r$ inclusive.

Let $f(l_1, r_1, l_2, r_2)$ be the number of different merging sequences of $x[l_1,r_1]$ and $y[l_2,r_2]$ that produce chaotic merges. Note that only non-empty substrings of $x$ and $y$ are considered.

Calculate $\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)$. Output the answer modulo $998\,244\,353$.

给你两个字符串 $x$ 和 $y$，它们均由小写拉丁字母组成。记 $|s|$ 为字符串 $s$ 的长度。

我们称一个序列 $a$ 为合并序列，若它恰好包含 $|x|$ 个 $0$ 和 $|y|$ 个 $1$（以某种顺序排列）。

由序列 $a$ 生成的合并串 $z$ 按如下规则构造：

• 若 $a_i = 0$，则从 $x$ 的开头移除一个字符，并将其追加到 $z$ 的末尾；
• 若 $a_i = 1$，则从 $y$ 的开头移除一个字符，并将其追加到 $z$ 的末尾。

两个合并序列 $a$ 和 $b$ 被称为不同，当且仅当存在某个位置 $i$，使得 $a_i \neq b_i$。

我们称一个字符串 $z$ 是混乱的（chaotic），若对所有 $i$ 满足 $2 \le i \le |z|$，均有 $z_{i-1} \neq z_i$。

对任意满足 $1 \le l \le r \le |s|$ 的整数 $l, r$，记 $s[l,r]$ 为字符串 $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$ 取模后输出。

The first line contains a string $x$ ($1 \le |x| \le 1000$).

The second line contains a string $y$ ($1 \le |y| \le 1000$).

Both strings consist only of lowercase Latin letters.

第一行包含一个字符串 $x$（$1 \le |x| \le 1000$）。

第二行包含一个字符串 $y$（$1 \le |y| \le 1000$）。

两个字符串均由小写拉丁字母组成。

Print a single integer — the sum of $f(l_1, r_1, l_2, r_2)$ over $1 \le l_1 \le r_1 \le |x|$ and $1 \le l_2 \le r_2 \le |y|$ modulo $998\,244\,353$.

输出一个整数——对所有满足 $1 \le l_1 \le r_1 \le |x|$ 和 $1 \le l_2 \le r_2 \le |y|$ 的四元组 $(l_1, r_1, l_2, r_2)$，求 $f(l_1, r_1, l_2, r_2)$ 的和，并对 $998\,244\,353$ 取模。

In the first example there are:

• $6$ pairs of substrings "a" and "b", each with valid merging sequences "01" and "10";
• $3$ pairs of substrings "a" and "bb", each with a valid merging sequence "101";
• $4$ pairs of substrings "aa" and "b", each with a valid merging sequence "010";
• $2$ pairs of substrings "aa" and "bb", each with valid merging sequences "0101" and "1010";
• $2$ pairs of substrings "aaa" and "b", each with no valid merging sequences;
• $1$ pair of substrings "aaa" and "bb" with a valid merging sequence "01010";

Thus, the answer is $6 \cdot 2 + 3 \cdot 1 + 4 \cdot 1 + 2 \cdot 2 + 2 \cdot 0 + 1 \cdot 1 = 24$.

在第一个例子中，存在：

• $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$。