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

#define rep(i,a,b) for(int i=(a),i##end=(b);i<=i##end;++i)
#define per(i,a,b) for(int i=(a),i##end=(b);i>=i##end;--i)
//mt19937 Rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
template<typename T>void chkmax(T&x,T y){if(x<y)x=y;}
template<typename T>void chkmin(T&x,T y){if(x>y)x=y;}
inline int read(){
  #define nc getchar()
  int x=0;char c=nc;bool f=0;
  while(c<48)f|=c=='-',c=nc;
  while(c>47)x=x*10+(c^48),c=nc;
  return f?-x:x;
  #undef nc
}

typedef double db;
typedef long long ll;
typedef vector<int>vi;
typedef pair<int,int>pii;
const int maxn=1010,P=998244353;
int Inc(int x,int y){return x+y<P?x+y:x+y-P;}
int Dec(int x,int y){return x<y?x-y+P:x-y;}
void Add(int &x,int y){x+=y;if(x>=P)x-=P;}
void Sub(int &x,int y){x-=y;if(x<0)x+=P;}
int qp(int a,int k){int res=1;for(;k;k>>=1,a=1ll*a*a%P)if(k&1)res=1ll*res*a%P;return res;}
int n,m,valA[maxn],valB[maxn],F[maxn][maxn],G[maxn][maxn];char A[maxn],B[maxn];

void solve(){
  scanf("%s%s",A+1,B+1),n=strlen(A+1),m=strlen(B+1);
  rep(i,1,n){
    per(k,i,1){
      valA[i]++;
      if(A[k]==A[k-1])break;
    }
  }
  rep(i,1,m){
    per(k,i,1){
      valB[i]++;
      if(B[k]==B[k-1])break;
    }
  }
  int ans=0;
  rep(i,1,n){
    rep(j,1,m){
      if(A[i]!=B[j]){
        F[i][j]=valB[j];
        G[i][j]=valA[i];
//        per(k,j,1){
//          F[i][j]++;
//          if(B[k]==B[k-1])break;
//        }
//        per(k,i,1){
//          G[i][j]++;
//          if(A[k]==A[k-1])break;
//        }
      }
//      F[i][j]=valB[A[i]-'a'][j];
//      G[i][j]=valA[B[j]-'a'][i];
      if(A[i]!=A[i-1])Add(F[i][j],(1ll*F[i-1][j])%P);
      if(A[i]!=B[j])Add(F[i][j],(1ll*G[i-1][j])%P);
      if(B[j]!=B[j-1])Add(G[i][j],(1ll*G[i][j-1])%P);
      if(B[j]!=A[i])Add(G[i][j],(1ll*F[i][j-1])%P);
//      printf("(%d %d) %d %d\n",i,j,F[i][j],G[i][j]);
      Add(ans,Inc(F[i][j],G[i][j]));
    }
  }
  cout<<ans<<endl;
}

signed main(){
//  int T=read();
//  while(T--)solve();
  solve();
  return 0;
}

### Prompt

Create a solution in cpp for 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 rep(i,a,b) for(int i=(a),i##end=(b);i<=i##end;++i)
#define per(i,a,b) for(int i=(a),i##end=(b);i>=i##end;--i)
//mt19937 Rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
template<typename T>void chkmax(T&x,T y){if(x<y)x=y;}
template<typename T>void chkmin(T&x,T y){if(x>y)x=y;}
inline int read(){
  #define nc getchar()
  int x=0;char c=nc;bool f=0;
  while(c<48)f|=c=='-',c=nc;
  while(c>47)x=x*10+(c^48),c=nc;
  return f?-x:x;
  #undef nc
}

typedef double db;
typedef long long ll;
typedef vector<int>vi;
typedef pair<int,int>pii;
const int maxn=1010,P=998244353;
int Inc(int x,int y){return x+y<P?x+y:x+y-P;}
int Dec(int x,int y){return x<y?x-y+P:x-y;}
void Add(int &x,int y){x+=y;if(x>=P)x-=P;}
void Sub(int &x,int y){x-=y;if(x<0)x+=P;}
int qp(int a,int k){int res=1;for(;k;k>>=1,a=1ll*a*a%P)if(k&1)res=1ll*res*a%P;return res;}
int n,m,valA[maxn],valB[maxn],F[maxn][maxn],G[maxn][maxn];char A[maxn],B[maxn];

void solve(){
  scanf("%s%s",A+1,B+1),n=strlen(A+1),m=strlen(B+1);
  rep(i,1,n){
    per(k,i,1){
      valA[i]++;
      if(A[k]==A[k-1])break;
    }
  }
  rep(i,1,m){
    per(k,i,1){
      valB[i]++;
      if(B[k]==B[k-1])break;
    }
  }
  int ans=0;
  rep(i,1,n){
    rep(j,1,m){
      if(A[i]!=B[j]){
        F[i][j]=valB[j];
        G[i][j]=valA[i];
//        per(k,j,1){
//          F[i][j]++;
//          if(B[k]==B[k-1])break;
//        }
//        per(k,i,1){
//          G[i][j]++;
//          if(A[k]==A[k-1])break;
//        }
      }
//      F[i][j]=valB[A[i]-'a'][j];
//      G[i][j]=valA[B[j]-'a'][i];
      if(A[i]!=A[i-1])Add(F[i][j],(1ll*F[i-1][j])%P);
      if(A[i]!=B[j])Add(F[i][j],(1ll*G[i-1][j])%P);
      if(B[j]!=B[j-1])Add(G[i][j],(1ll*G[i][j-1])%P);
      if(B[j]!=A[i])Add(G[i][j],(1ll*F[i][j-1])%P);
//      printf("(%d %d) %d %d\n",i,j,F[i][j],G[i][j]);
      Add(ans,Inc(F[i][j],G[i][j]));
    }
  }
  cout<<ans<<endl;
}

signed main(){
//  int T=read();
//  while(T--)solve();
  solve();
  return 0;
}

```