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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

const int mod=998244353;
inline void add(int &a,int b){
    a+=b;
    if(a>=mod)a-=mod;
}
int dp[222222][3][4];

signed main(){
    string S;
    cin>>S;

    rep(i,3)dp[1][i][i]=1;
    for(int i=1;i<S.size();i++){
        rep(j,3){
            rep(k,4){
                rep(l,3){
                    if(k==3){
                        add(dp[i+1][(j+l)%3][3],dp[i][j][k]);
                    }
                    else{
                        if(k==l)add(dp[i+1][(j+l)%3][3],dp[i][j][k]);
                        else add(dp[i+1][(j+l)%3][l],dp[i][j][k]);
                    }
                }
            }
        }
    }

    int m=0;
    rep(i,S.size())m=(m+S[i]-'a')%3;

    if(count(all(S),S[0])==S.size()){
        cout<<1<<endl;
        return 0;
    }

    if(S.size()==3&&m==0){
        cout<<3<<endl;
        return 0;
    }

    bool flag=true;
    rep(i,S.size())if(S[i+1]==S[i])flag=false;

    int ans=dp[S.size()][m][3];
    if(flag)ans=(ans+1)%mod;
    cout<<ans<<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>
using namespace std;

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

const int mod=998244353;
inline void add(int &a,int b){
    a+=b;
    if(a>=mod)a-=mod;
}
int dp[222222][3][4];

signed main(){
    string S;
    cin>>S;

    rep(i,3)dp[1][i][i]=1;
    for(int i=1;i<S.size();i++){
        rep(j,3){
            rep(k,4){
                rep(l,3){
                    if(k==3){
                        add(dp[i+1][(j+l)%3][3],dp[i][j][k]);
                    }
                    else{
                        if(k==l)add(dp[i+1][(j+l)%3][3],dp[i][j][k]);
                        else add(dp[i+1][(j+l)%3][l],dp[i][j][k]);
                    }
                }
            }
        }
    }

    int m=0;
    rep(i,S.size())m=(m+S[i]-'a')%3;

    if(count(all(S),S[0])==S.size()){
        cout<<1<<endl;
        return 0;
    }

    if(S.size()==3&&m==0){
        cout<<3<<endl;
        return 0;
    }

    bool flag=true;
    rep(i,S.size())if(S[i+1]==S[i])flag=false;

    int ans=dp[S.size()][m][3];
    if(flag)ans=(ans+1)%mod;
    cout<<ans<<endl;
    return 0;
}

```