#P1499E. Chaotic Merge

Chaotic Merge

Description

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$.

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.

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$.

Input

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.

Output

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$.

Samples

aaa
bb
24
code
forces
1574
aaaaa
aaa
0
justamassivetesttocheck
howwellyouhandlemodulooperations
667387032

Note

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$.