#include <bits/stdc++.h>
using namespace std;

#define nl "\n"
#define nf endl
#define ll long long
#define pb push_back
#define _ << ' ' <<

#define INF (ll)1e18
#define mod 998244353
#define maxn 1010

ll i, i1, j, k, k1, t, n, m, res, flag[10], dp[maxn][maxn][3][2][2], l, v0, v1;
string a, b;
char c1, c2;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    #if !ONLINE_JUDGE && !EVAL
        ifstream cin("input.txt");
        ofstream cout("output.txt");
    #endif

    cin >> a >> b; n = a.size(); m = b.size(); a = '#' + a; b = '#' + b;

    for (i = 0; i <= n; i++) {
        for (j = 0; j <= m; j++) {
            dp[i][j][2][0][0] = 1;
        }
    }

    /* for (j = 1; j <= m; j++) dp[0][j][1] = 1;
    for (i = 1; i <= n; i++) dp[i][0][0] = 1; */

    for (i = 0; i <= n; i++) {
        for (j = 0; j <= m; j++) {
            for (k = 0; k <= 1; k++) {
                if (i + k == 0) continue;
                if (j - k + 1 == 0) continue;
                // cout << i _ j _ k _ dp[i][j][k] << nl;
                for (l = 0; l <= 2; l++) {
                    for (v0 = 0; v0 <= 1; v0++) {
                        for (v1 = 0; v1 <= 1; v1++) {
                            if (l == 0 && v0 == 0) continue;
                            if (l == 1 && v1 == 0) continue;
                            if (l != 2) {
                                if (k == 0) c1 = a[i];
                                else c1 = b[j];
                                if (l == 0) c2 = a[i - (k == 0)];
                                else c2 = b[j - (k == 1)];
                                // cout << c1 _ c2 << nl;
                                if (c1 == c2) continue;
                            }
                            dp[i][j][k][max(v0, (ll)(k == 0))][max(v1, (ll)(k == 1))] += dp[i - (ll)(k == 0)][j - (ll)(k == 1)][l][v0][v1];
                            dp[i][j][k][max(v0, (ll)(k == 0))][max(v1, (ll)(k == 1))] %= mod;
                            if (min(max(v0, (ll)(k == 0)), max(v1, (ll)(k == 1))) > 0) {
                                // cout << dp[i - (k == 0)][j - (k == 1)][l] << nl;
                                res += dp[i - (k == 0)][j - (k == 1)][l][v0][v1];
                                res %= mod;
                            }
                        }
                    }
                }
                // cout << i _ j _ k _ dp[i][j][k] << nl;
                // cout << nl;
            }
        }
    }

    cout << res << nl;

    return 0;
}

### Prompt

Generate a Cpp solution to the following problem:

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 ≠ b_i.

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

Let s[l,r] for some 1 ≤ l ≤ r ≤ |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 ∑ _{1 ≤ l_1 ≤ r_1 ≤ |x| \\\ 1 ≤ l_2 ≤ r_2 ≤ |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 ≤ |x| ≤ 1000).

The second line contains a string y (1 ≤ |y| ≤ 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 ≤ l_1 ≤ r_1 ≤ |x| and 1 ≤ l_2 ≤ r_2 ≤ |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 ⋅ 2 + 3 ⋅ 1 + 4 ⋅ 1 + 2 ⋅ 2 + 2 ⋅ 0 + 1 ⋅ 1 = 24.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;

#define nl "\n"
#define nf endl
#define ll long long
#define pb push_back
#define _ << ' ' <<

#define INF (ll)1e18
#define mod 998244353
#define maxn 1010

ll i, i1, j, k, k1, t, n, m, res, flag[10], dp[maxn][maxn][3][2][2], l, v0, v1;
string a, b;
char c1, c2;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    #if !ONLINE_JUDGE && !EVAL
        ifstream cin("input.txt");
        ofstream cout("output.txt");
    #endif

    cin >> a >> b; n = a.size(); m = b.size(); a = '#' + a; b = '#' + b;

    for (i = 0; i <= n; i++) {
        for (j = 0; j <= m; j++) {
            dp[i][j][2][0][0] = 1;
        }
    }

    /* for (j = 1; j <= m; j++) dp[0][j][1] = 1;
    for (i = 1; i <= n; i++) dp[i][0][0] = 1; */

    for (i = 0; i <= n; i++) {
        for (j = 0; j <= m; j++) {
            for (k = 0; k <= 1; k++) {
                if (i + k == 0) continue;
                if (j - k + 1 == 0) continue;
                // cout << i _ j _ k _ dp[i][j][k] << nl;
                for (l = 0; l <= 2; l++) {
                    for (v0 = 0; v0 <= 1; v0++) {
                        for (v1 = 0; v1 <= 1; v1++) {
                            if (l == 0 && v0 == 0) continue;
                            if (l == 1 && v1 == 0) continue;
                            if (l != 2) {
                                if (k == 0) c1 = a[i];
                                else c1 = b[j];
                                if (l == 0) c2 = a[i - (k == 0)];
                                else c2 = b[j - (k == 1)];
                                // cout << c1 _ c2 << nl;
                                if (c1 == c2) continue;
                            }
                            dp[i][j][k][max(v0, (ll)(k == 0))][max(v1, (ll)(k == 1))] += dp[i - (ll)(k == 0)][j - (ll)(k == 1)][l][v0][v1];
                            dp[i][j][k][max(v0, (ll)(k == 0))][max(v1, (ll)(k == 1))] %= mod;
                            if (min(max(v0, (ll)(k == 0)), max(v1, (ll)(k == 1))) > 0) {
                                // cout << dp[i - (k == 0)][j - (k == 1)][l] << nl;
                                res += dp[i - (k == 0)][j - (k == 1)][l][v0][v1];
                                res %= mod;
                            }
                        }
                    }
                }
                // cout << i _ j _ k _ dp[i][j][k] << nl;
                // cout << nl;
            }
        }
    }

    cout << res << nl;

    return 0;
}

```