#include<bits/stdc++.h> 
#define int long long
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define endl "\n"
using namespace std;

const int max_n = 1e3+100;
const int max_value = 1e6+10;
const int inf = 1e18;
const long long Mod = 998244353;

int n,m;
string x,y;
int dp[max_n][max_n][3];

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin>>x>>y;
    n=x.size();
    m=y.size();

    for(int i=n;i>=0;i--){
        for(int j=m;j>=0;j--){
            for(int prev=0;prev<3;prev++){

                if(prev==0){
                    dp[i][j][prev]=1;
                    
                    if(i<n && (i==0 || (x[i-1]!=x[i]))){
                        dp[i][j][prev]+=dp[i+1][j][0];
                    }
                    if(j<m && (i==0 || (x[i-1]!=y[j]))){
                        dp[i][j][prev]+=dp[i][j+1][1];
                    }

                }else if(prev==1){
                    dp[i][j][prev]=1;

                    if(i<n && (j==0 || (y[j-1]!=x[i]))){
                        dp[i][j][prev]+=dp[i+1][j][0];
                    }
                    if(j<m && (j==0 || (y[j-1]!=y[j]))){
                        dp[i][j][prev]+=dp[i][j+1][1];
                    }

                }else if(prev==2){
                    dp[i][j][prev]=(dp[i+1][j][0]+dp[i][j+1][1])%Mod;
                }

                dp[i][j][prev]%=Mod;
            }
        }
    }

    int ans=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            ans+=dp[i][j][2];
            ans%=Mod;
        }
    }

    int cur=0;
    for(int i=0;i<n;i++){
        if(i>0 && x[i]==x[i-1]){
            int C = ((cur*(cur+1))/2)%Mod;
            C = (C*m)%Mod;
            ans = (ans-C+Mod)%Mod;

            cur=1;
        }else{
            cur++;
        }
    }
    int C = ((cur*(cur+1))/2)%Mod;
    C = (C*m)%Mod;
    ans = (ans-C+Mod)%Mod;

    cur=0;
    for(int i=0;i<m;i++){
        if(i>0 && y[i]==y[i-1]){
            int C = ((cur*(cur+1))/2)%Mod;
            C = (C*n)%Mod;
            ans = (ans-C+Mod)%Mod;

            cur=1;
        }else{
            cur++;
        }
    }
    C = ((cur*(cur+1))/2)%Mod;
    C = (C*n)%Mod;
    ans = (ans-C+Mod)%Mod;


    cout<<ans<<endl;

}
### Prompt

Construct a Cpp code solution to the problem outlined:

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> 
#define int long long
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define endl "\n"
using namespace std;

const int max_n = 1e3+100;
const int max_value = 1e6+10;
const int inf = 1e18;
const long long Mod = 998244353;

int n,m;
string x,y;
int dp[max_n][max_n][3];

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin>>x>>y;
    n=x.size();
    m=y.size();

    for(int i=n;i>=0;i--){
        for(int j=m;j>=0;j--){
            for(int prev=0;prev<3;prev++){

                if(prev==0){
                    dp[i][j][prev]=1;
                    
                    if(i<n && (i==0 || (x[i-1]!=x[i]))){
                        dp[i][j][prev]+=dp[i+1][j][0];
                    }
                    if(j<m && (i==0 || (x[i-1]!=y[j]))){
                        dp[i][j][prev]+=dp[i][j+1][1];
                    }

                }else if(prev==1){
                    dp[i][j][prev]=1;

                    if(i<n && (j==0 || (y[j-1]!=x[i]))){
                        dp[i][j][prev]+=dp[i+1][j][0];
                    }
                    if(j<m && (j==0 || (y[j-1]!=y[j]))){
                        dp[i][j][prev]+=dp[i][j+1][1];
                    }

                }else if(prev==2){
                    dp[i][j][prev]=(dp[i+1][j][0]+dp[i][j+1][1])%Mod;
                }

                dp[i][j][prev]%=Mod;
            }
        }
    }

    int ans=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            ans+=dp[i][j][2];
            ans%=Mod;
        }
    }

    int cur=0;
    for(int i=0;i<n;i++){
        if(i>0 && x[i]==x[i-1]){
            int C = ((cur*(cur+1))/2)%Mod;
            C = (C*m)%Mod;
            ans = (ans-C+Mod)%Mod;

            cur=1;
        }else{
            cur++;
        }
    }
    int C = ((cur*(cur+1))/2)%Mod;
    C = (C*m)%Mod;
    ans = (ans-C+Mod)%Mod;

    cur=0;
    for(int i=0;i<m;i++){
        if(i>0 && y[i]==y[i-1]){
            int C = ((cur*(cur+1))/2)%Mod;
            C = (C*n)%Mod;
            ans = (ans-C+Mod)%Mod;

            cur=1;
        }else{
            cur++;
        }
    }
    C = ((cur*(cur+1))/2)%Mod;
    C = (C*n)%Mod;
    ans = (ans-C+Mod)%Mod;


    cout<<ans<<endl;

}
```