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

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

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