#include<bits/stdc++.h>
#define maxn 340000
#define M 998244353
 
using namespace std;
typedef long long ll;
ll dp[maxn][3][3],n,t,f,ans,g;
char s[maxn];
 
int main()
{
    scanf("%s",s); n=strlen(s); ans=1; g=1;
    f=1; for (int i=1;i<n;i++) f&=s[i]!=s[i-1],g&=s[i]==s[i-1],ans=ans*3%M;
    if (g) {cout << 1 << endl; return 0;}
    if (n==2) {cout << 1+(s[0]!=s[1]) << endl;return 0;}
    if (n==3) {
        if (s[0]==s[1]&&s[0]==s[2]) cout << 1 << endl;
        else if (s[0]!=s[1]&&s[1]!=s[2]&&s[0]!=s[2]) cout << 3 << endl;
        else cout << 6+f << endl;
        return 0;
    }
    for (int i=0;i<n;i++) t=(t+s[i]-'a')%3;
    for (int i=0;i<3;i++) dp[1][i][i]=1;
    for (int i=2;i<=n;i++)
        for (int j=0;j<3;j++)
            for (int k=0;k<3;k++)
                for (int l=0;l<3;l++)
                    if (k!=l) (dp[i][(j+l)%3][l]+=dp[i-1][j][k])%=M;
    cout << ((ans-dp[n][t][0]-dp[n][t][1]-dp[n][t][2])%M+M+f)%M << endl;
    return 0;
}
### Prompt

Your challenge is to write 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>
#define maxn 340000
#define M 998244353
 
using namespace std;
typedef long long ll;
ll dp[maxn][3][3],n,t,f,ans,g;
char s[maxn];
 
int main()
{
    scanf("%s",s); n=strlen(s); ans=1; g=1;
    f=1; for (int i=1;i<n;i++) f&=s[i]!=s[i-1],g&=s[i]==s[i-1],ans=ans*3%M;
    if (g) {cout << 1 << endl; return 0;}
    if (n==2) {cout << 1+(s[0]!=s[1]) << endl;return 0;}
    if (n==3) {
        if (s[0]==s[1]&&s[0]==s[2]) cout << 1 << endl;
        else if (s[0]!=s[1]&&s[1]!=s[2]&&s[0]!=s[2]) cout << 3 << endl;
        else cout << 6+f << endl;
        return 0;
    }
    for (int i=0;i<n;i++) t=(t+s[i]-'a')%3;
    for (int i=0;i<3;i++) dp[1][i][i]=1;
    for (int i=2;i<=n;i++)
        for (int j=0;j<3;j++)
            for (int k=0;k<3;k++)
                for (int l=0;l<3;l++)
                    if (k!=l) (dp[i][(j+l)%3][l]+=dp[i-1][j][k])%=M;
    cout << ((ans-dp[n][t][0]-dp[n][t][1]-dp[n][t][2])%M+M+f)%M << endl;
    return 0;
}
```