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

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef vector<LL> VI;
typedef unsigned long long ULL;

#define MP make_pair
#define PB push_back
#define FOR(i, a, b) for (int i = (a); i<(b); ++i)
#define RFOR(i, b, a) for (int i = (b)-1; i>=(a); --i)
#define ALL(a) a.begin(), a.end()
#define SZ(a) (int)a.size()
#define f first
#define s second
#define FILL(a, b) memset(a, b, sizeof(a))

const int MAX = 200*1000 + 7;
const int INF = 1000*1000*1000;
const LL LINF = 1LL*INF*INF;
const int MOD = 998244353;
const double PI = acos(-1.);

LL dpT1[MAX][3];
LL dp1(int n, int ost)
{
	if(n==0)
	{
		return (ost==0);
	}
	if(dpT1[n][ost] != -1)
		return dpT1[n][ost];
	LL ans = 0;
	FOR(i, 0, 3)
	{
		ans += dp1(n-1, (ost + 3 - i)%3);
	}
	return dpT1[n][ost] = ans % MOD;
}
LL dpT2[MAX][3][4];
LL dp2(int n, int ost, int prev)
{
	if(n==0)
	{
		return (ost==0);
	}
	if(dpT2[n][ost][prev] != -1)
		return dpT2[n][ost][prev];
	LL ans = 0;
	FOR(i, 0, 3)
	{
		if(i != prev)
			ans += dp2(n-1, (ost + 3 - i)%3, i);
	}
	return dpT2[n][ost][prev] = ans% MOD;
}

int cnt = 0;
map<string, int> used;
void dfs(string s)
{
	cnt++;
	used[s] = 1;
	FOR(i,0,SZ(s)-1)
	{
		if(s[i] != s[i+1])
		{
			string ns = s;
			int ind = 3 - (s[i]-'a') - (s[i+1]-'a');
			ns[i] = char(int('a') + ind);
			ns[i+1] = char(int('a') + ind);
			if(!used[ns])
				dfs(ns);
		}
	}
}
int brut(string s)
{
	dfs(s);
	return cnt;
}
int main()
{
	ios_base::sync_with_stdio(0);
	string s;
	cin >> s;
	bool ok = 1;
	FOR(i,0,SZ(s))
		if(s[i]!= s[0])
			ok = 0;
	if(ok)
	{
		cout << 1;
		return 0;
	}
	if(SZ(s)!=3)
	{
		FILL(dpT1, -1);
		FILL(dpT2, -1);
		int ost = 0;
		FOR(i,0,SZ(s))
			ost += (s[i] - 'a');
		ost %= 3;
		int no_double = 1;
		FOR(i,0,SZ(s) - 1)
			if(s[i]==s[i+1])
				no_double = 0;
		cout << (dp1(SZ(s), ost) + MOD - dp2(SZ(s), ost, 3) + no_double)%MOD;
	}
	else
	{
		cout << brut(s);
	}
	return 0;
}

### Prompt

Please formulate a CPP solution to the following problem:

You are given a string S consisting of `a`,`b` and `c`. Find the number of strings that can be possibly obtained by repeatedly performing the following operation zero or more times, modulo 998244353:

* Choose an integer i such that 1\leq i\leq |S|-1 and the i-th and (i+1)-th characters in S are different. Replace each of the i-th and (i+1)-th characters in S with the character that differs from both of them (among `a`, `b` and `c`).

Constraints

* 2 \leq |S| \leq 2 × 10^5
* S consists of `a`, `b` and `c`.

Input

Input is given from Standard Input in the following format:


S


Output

Print the number of strings that can be possibly obtained by repeatedly performing the operation, modulo 998244353.

Examples

Input

abc


Output

3


Input

abbac


Output

65


Input

babacabac


Output

6310


Input

ababacbcacbacacbcbbcbbacbaccacbacbacba


Output

148010497

### Response

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

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef vector<LL> VI;
typedef unsigned long long ULL;

#define MP make_pair
#define PB push_back
#define FOR(i, a, b) for (int i = (a); i<(b); ++i)
#define RFOR(i, b, a) for (int i = (b)-1; i>=(a); --i)
#define ALL(a) a.begin(), a.end()
#define SZ(a) (int)a.size()
#define f first
#define s second
#define FILL(a, b) memset(a, b, sizeof(a))

const int MAX = 200*1000 + 7;
const int INF = 1000*1000*1000;
const LL LINF = 1LL*INF*INF;
const int MOD = 998244353;
const double PI = acos(-1.);

LL dpT1[MAX][3];
LL dp1(int n, int ost)
{
	if(n==0)
	{
		return (ost==0);
	}
	if(dpT1[n][ost] != -1)
		return dpT1[n][ost];
	LL ans = 0;
	FOR(i, 0, 3)
	{
		ans += dp1(n-1, (ost + 3 - i)%3);
	}
	return dpT1[n][ost] = ans % MOD;
}
LL dpT2[MAX][3][4];
LL dp2(int n, int ost, int prev)
{
	if(n==0)
	{
		return (ost==0);
	}
	if(dpT2[n][ost][prev] != -1)
		return dpT2[n][ost][prev];
	LL ans = 0;
	FOR(i, 0, 3)
	{
		if(i != prev)
			ans += dp2(n-1, (ost + 3 - i)%3, i);
	}
	return dpT2[n][ost][prev] = ans% MOD;
}

int cnt = 0;
map<string, int> used;
void dfs(string s)
{
	cnt++;
	used[s] = 1;
	FOR(i,0,SZ(s)-1)
	{
		if(s[i] != s[i+1])
		{
			string ns = s;
			int ind = 3 - (s[i]-'a') - (s[i+1]-'a');
			ns[i] = char(int('a') + ind);
			ns[i+1] = char(int('a') + ind);
			if(!used[ns])
				dfs(ns);
		}
	}
}
int brut(string s)
{
	dfs(s);
	return cnt;
}
int main()
{
	ios_base::sync_with_stdio(0);
	string s;
	cin >> s;
	bool ok = 1;
	FOR(i,0,SZ(s))
		if(s[i]!= s[0])
			ok = 0;
	if(ok)
	{
		cout << 1;
		return 0;
	}
	if(SZ(s)!=3)
	{
		FILL(dpT1, -1);
		FILL(dpT2, -1);
		int ost = 0;
		FOR(i,0,SZ(s))
			ost += (s[i] - 'a');
		ost %= 3;
		int no_double = 1;
		FOR(i,0,SZ(s) - 1)
			if(s[i]==s[i+1])
				no_double = 0;
		cout << (dp1(SZ(s), ost) + MOD - dp2(SZ(s), ost, 3) + no_double)%MOD;
	}
	else
	{
		cout << brut(s);
	}
	return 0;
}

```