#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <bitset>
#include <string>
#include <cmath>
#include <set>
#include <map>
#define Rep(i, x, y) for (int i = x; i <= y; i ++)
#define Dwn(i, x, y) for (int i = x; i >= y; i --)
#define RepE(i, x) for (int i = pos[x]; i; i = g[i].nex)
#define ev g[i].y
#define eps 1e-10
#define fr first
#define sd second
#define pb push_back
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
const int N = 200005, mod = 998244353;
int n, m, T, q, k, f1, f2;
char s[N];
ll ans;
ll power(ll x, int y) {
	ll z = 1;
	while (y) {
		if (y & 1) (z *= x) %= mod;
		y >>= 1; (x *= x) %= mod;
	}
	return z;
}
int main()
{
	scanf ("%s", s + 1);
	n = strlen(s + 1);
	Rep(i, 1, n) {
		k += s[i] - 'a';
	}
//	cout <<k<<endl;
	ans = (power(3, n - 1) - power(2, n - 1) + mod) % mod;
	Rep(i, 1, n - 1) {
		if (s[i] != s[i + 1]) f1 = 1;
		if (s[i] == s[i + 1]) f2 = 1;
	}
	if (!f1) {
		puts("1");
		return 0;
	}
	if (n == 3 && k == 3) {
		puts("3");
		return 0;
	}
	ans += !f2;
	if (n % 3 == 0) {
		ll z = power(2, n / 3 - 1); // % mod;
		if (k % 3 == 0) ans -= z * 2 % mod;
		else ans += z;
	}
	printf("%lld\n", (ans + mod) % mod);
	return 0;
}
### Prompt

Construct a Cpp code solution to the problem outlined:

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 <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <bitset>
#include <string>
#include <cmath>
#include <set>
#include <map>
#define Rep(i, x, y) for (int i = x; i <= y; i ++)
#define Dwn(i, x, y) for (int i = x; i >= y; i --)
#define RepE(i, x) for (int i = pos[x]; i; i = g[i].nex)
#define ev g[i].y
#define eps 1e-10
#define fr first
#define sd second
#define pb push_back
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
const int N = 200005, mod = 998244353;
int n, m, T, q, k, f1, f2;
char s[N];
ll ans;
ll power(ll x, int y) {
	ll z = 1;
	while (y) {
		if (y & 1) (z *= x) %= mod;
		y >>= 1; (x *= x) %= mod;
	}
	return z;
}
int main()
{
	scanf ("%s", s + 1);
	n = strlen(s + 1);
	Rep(i, 1, n) {
		k += s[i] - 'a';
	}
//	cout <<k<<endl;
	ans = (power(3, n - 1) - power(2, n - 1) + mod) % mod;
	Rep(i, 1, n - 1) {
		if (s[i] != s[i + 1]) f1 = 1;
		if (s[i] == s[i + 1]) f2 = 1;
	}
	if (!f1) {
		puts("1");
		return 0;
	}
	if (n == 3 && k == 3) {
		puts("3");
		return 0;
	}
	ans += !f2;
	if (n % 3 == 0) {
		ll z = power(2, n / 3 - 1); // % mod;
		if (k % 3 == 0) ans -= z * 2 % mod;
		else ans += z;
	}
	printf("%lld\n", (ans + mod) % mod);
	return 0;
}
```