#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <vector>
//#define ivorysi
#define MAXN 200005
#define eps 1e-7
#define mo 974711
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
const int64 MOD = 998244353;
int N;
char s[MAXN];
int64 dp[MAXN][3][3][2];
void inc(int64 &x,int64 y) {
    x = x + y;
    while(x >= MOD) x -= MOD;
}
     
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    scanf("%s",s + 1);
    N = strlen(s + 1);
    bool all_same = 1;
    for(int i = 1 ; i <= N ; ++i) {
    	if(s[i] != s[1]) all_same = 0;
    }
    if(all_same) {puts("1");return 0;}
    if(N > 3) {
    	for(int i = 0 ; i <= 2 ; ++i) dp[1][i][i][0] = 1;
    	for(int i = 2 ; i <= N ; ++i) {
    	    for(int s = 0 ; s <= 2 ; ++s) {
    		for(int j = 0 ; j <= 2 ; ++j) {
    		    for(int h = 0 ; h <= 2 ; ++h) {
    			for(int l = 0 ; l <= 1 ; ++l) {
    			    inc(dp[i][(s + h) % 3][h][l || h == j],dp[i - 1][s][j][l]);
    			}
    		    }
    		}
    	    }
    	}
    	bool flag = 1;
    	int c = 0;
    	for(int i = 1 ; i <= N ; ++i) {
    	    c = (c + s[i] - 'a') % 3;
    	}
    	for(int i = 2 ; i <= N ; ++i) {
    	    if(s[i] == s[i - 1]) {flag = 0;break;}
    	}
    	int64 ans = flag;
    	for(int i = 0 ; i <= 2 ; ++i) ans += dp[N][c][i][1];
    	ans %= MOD;
    	printf("%lld\n",ans);
    }
    else {
    	if(N == 3) {
    	    if(s[1] != s[2] && s[2] != s[3] && s[1] != s[3]) puts("3");
    	    else if(s[1] == s[2] || s[2] == s[3]) puts("6");
    	    else puts("7");
    	}
    	else if(N == 2) {
    	    puts("2");
    	}
    }
    return 0;
}
### Prompt

Your task is to create 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 <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <vector>
//#define ivorysi
#define MAXN 200005
#define eps 1e-7
#define mo 974711
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
const int64 MOD = 998244353;
int N;
char s[MAXN];
int64 dp[MAXN][3][3][2];
void inc(int64 &x,int64 y) {
    x = x + y;
    while(x >= MOD) x -= MOD;
}
     
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    scanf("%s",s + 1);
    N = strlen(s + 1);
    bool all_same = 1;
    for(int i = 1 ; i <= N ; ++i) {
    	if(s[i] != s[1]) all_same = 0;
    }
    if(all_same) {puts("1");return 0;}
    if(N > 3) {
    	for(int i = 0 ; i <= 2 ; ++i) dp[1][i][i][0] = 1;
    	for(int i = 2 ; i <= N ; ++i) {
    	    for(int s = 0 ; s <= 2 ; ++s) {
    		for(int j = 0 ; j <= 2 ; ++j) {
    		    for(int h = 0 ; h <= 2 ; ++h) {
    			for(int l = 0 ; l <= 1 ; ++l) {
    			    inc(dp[i][(s + h) % 3][h][l || h == j],dp[i - 1][s][j][l]);
    			}
    		    }
    		}
    	    }
    	}
    	bool flag = 1;
    	int c = 0;
    	for(int i = 1 ; i <= N ; ++i) {
    	    c = (c + s[i] - 'a') % 3;
    	}
    	for(int i = 2 ; i <= N ; ++i) {
    	    if(s[i] == s[i - 1]) {flag = 0;break;}
    	}
    	int64 ans = flag;
    	for(int i = 0 ; i <= 2 ; ++i) ans += dp[N][c][i][1];
    	ans %= MOD;
    	printf("%lld\n",ans);
    }
    else {
    	if(N == 3) {
    	    if(s[1] != s[2] && s[2] != s[3] && s[1] != s[3]) puts("3");
    	    else if(s[1] == s[2] || s[2] == s[3]) puts("6");
    	    else puts("7");
    	}
    	else if(N == 2) {
    	    puts("2");
    	}
    }
    return 0;
}
```