//To debug :  g++ -g file.cpp -o code
//to flush output : fflush(stdout) or cout.flush()
//cout<<setprecision(p)<<fixed<<var
//use 1LL<<i to for 64 bit shifting , (ll)2 because by default 2 is ll
//take care of precedence rule of operators 
//do not forget to change the sizes of arrays and value of contants and other things after debugging  
 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,a,n) for(i=a;i<n;++i)
#define irep(i,n,a) for(i=n;i>a;--i)
#define mod 1000000007
#define pb push_back
#define big 9223372036854775807
#define big1 LONG_MAX
#define big2 ll_MAX
#define big3 1000000000
#define sma1 LONG_MIN
#define sma2 ll_MIN
#define sma3 -1000000000
#define mp make_pair
#define dub double
#define ivec vector<ll>
#define lvec vector<long long>
#define cvec vector<char>
#define svec vector<string>
#define mt make_tuple
#define MOD 998244353
#define ld long double
#define pi acos(-1.0)
 
#define SZ(x)  (ll)(x.size())
 
//comment the below if not required
 
/*
 
#define ss second.second
#define ff first.first
#define f first
#define s second
#define sf second.first
#define fs first.second
*/
 
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
 
//cout<<"Case #"<<c<<": "<<ans<<"\n" ;

const ll N = 1000;

ll ans[N][N][2][4],n,m,i,j,k,o=1,res;

string a,b;

void add(ll &a,ll &b)
{
	a = (a+b)%MOD;
}

int main()
{
	IOS;

	cin>>a>>b;
	n=SZ(a),m=SZ(b);


	for(i=0;i<n;++i)
	{
		for(j=0;j<m;++j)
		{
			//suppose we choose to end at i
			// the previous one could be either i-1 or j

			ans[i][j][0][1]=1;
			if((i-1)>=0 && a[i]!=a[i-1])
			{
				for(k=1;k<=3;++k)
					add(ans[i][j][0][1|k],ans[i-1][j][0][k]);
			}

			
			ans[i][j][1][2]=1;
			if((j-1)>=0 && b[j]!=b[j-1])
			{
				for(k=1;k<=3;++k)
					add(ans[i][j][1][2|k],ans[i][j-1][1][k]);
			}

			if(a[i]!=b[j])
			{
				if((i-1)>=0)
					for(k=1;k<=3;++k)
						add(ans[i][j][0][3],ans[i-1][j][1][k]);
				else
					add(ans[i][j][0][3],ans[i][j][1][2]);
				if((j-1)>=0)
				for(k=1;k<=3;++k)
					add(ans[i][j][1][3],ans[i][j-1][0][k]);
				else
					add(ans[i][j][1][3],ans[i][j][0][1]);
			}

			add(res,ans[i][j][0][3]);
			add(res,ans[i][j][1][3]);

		}
	}

	cout<<res<<"\n";


	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
//To debug :  g++ -g file.cpp -o code
//to flush output : fflush(stdout) or cout.flush()
//cout<<setprecision(p)<<fixed<<var
//use 1LL<<i to for 64 bit shifting , (ll)2 because by default 2 is ll
//take care of precedence rule of operators 
//do not forget to change the sizes of arrays and value of contants and other things after debugging  
 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,a,n) for(i=a;i<n;++i)
#define irep(i,n,a) for(i=n;i>a;--i)
#define mod 1000000007
#define pb push_back
#define big 9223372036854775807
#define big1 LONG_MAX
#define big2 ll_MAX
#define big3 1000000000
#define sma1 LONG_MIN
#define sma2 ll_MIN
#define sma3 -1000000000
#define mp make_pair
#define dub double
#define ivec vector<ll>
#define lvec vector<long long>
#define cvec vector<char>
#define svec vector<string>
#define mt make_tuple
#define MOD 998244353
#define ld long double
#define pi acos(-1.0)
 
#define SZ(x)  (ll)(x.size())
 
//comment the below if not required
 
/*
 
#define ss second.second
#define ff first.first
#define f first
#define s second
#define sf second.first
#define fs first.second
*/
 
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
 
//cout<<"Case #"<<c<<": "<<ans<<"\n" ;

const ll N = 1000;

ll ans[N][N][2][4],n,m,i,j,k,o=1,res;

string a,b;

void add(ll &a,ll &b)
{
	a = (a+b)%MOD;
}

int main()
{
	IOS;

	cin>>a>>b;
	n=SZ(a),m=SZ(b);


	for(i=0;i<n;++i)
	{
		for(j=0;j<m;++j)
		{
			//suppose we choose to end at i
			// the previous one could be either i-1 or j

			ans[i][j][0][1]=1;
			if((i-1)>=0 && a[i]!=a[i-1])
			{
				for(k=1;k<=3;++k)
					add(ans[i][j][0][1|k],ans[i-1][j][0][k]);
			}

			
			ans[i][j][1][2]=1;
			if((j-1)>=0 && b[j]!=b[j-1])
			{
				for(k=1;k<=3;++k)
					add(ans[i][j][1][2|k],ans[i][j-1][1][k]);
			}

			if(a[i]!=b[j])
			{
				if((i-1)>=0)
					for(k=1;k<=3;++k)
						add(ans[i][j][0][3],ans[i-1][j][1][k]);
				else
					add(ans[i][j][0][3],ans[i][j][1][2]);
				if((j-1)>=0)
				for(k=1;k<=3;++k)
					add(ans[i][j][1][3],ans[i][j-1][0][k]);
				else
					add(ans[i][j][1][3],ans[i][j][0][1]);
			}

			add(res,ans[i][j][0][3]);
			add(res,ans[i][j][1][3]);

		}
	}

	cout<<res<<"\n";


	return 0;
}
```