Want to solve the contest problems after the official contest ends? Just register for practice and you will be able to submit solutions.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Chaotic Merge

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

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

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

Examples

Input

aaa bb

Output

24

Input

code forces

Output

1574

Input

aaaaa aaa

Output

0

Input

justamassivetesttocheck howwellyouhandlemodulooperations

Output

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

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/02/2021 04:23:37 (g2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|