#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <utility>
#include <queue>
#include <set>
#include <map>
#include <deque>
#include <iomanip>
#include <cstdio>
#include <stack>
#include <numeric>

using namespace std;
typedef  long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define  MP make_pair
#define  PB push_back
#define inf 1000000007
#define mod 998244353
#define rep(i,n) for(int i=0;i<(int)(n);++i)
set<string> st;int n;
char ch[]={'a','b','c'};
void dfs(string s){
    rep(i,n-1){
        if(s[i]!=s[i+1]){
            int c;
            rep(k,3){
                if(s[i]!=ch[k]&&s[i+1]!=ch[k]){
                    c = k;
                }
            }
            string t = s;
            t[i] = ch[c];
            t[i+1] = ch[c];
            if(st.count(t)==0){
                st.insert(t);
                dfs(t);
            }
        }
    }


}
ll dp[200010][3][3][2];
int main(){
    string s;
    cin >> s;
    n = s.size();
    if(n<=5){
        st.insert(s);
        dfs(s);
        for(auto x:st){
            cerr << x << endl;
        }
        cout << st.size() << endl;
        return 0;
    }
    set<char>ttt;
    int c = 0;
    bool flag = 1;
    rep(i,n-1){
        if(s[i]==s[i+1])flag = 0;
    }
    rep(i,n){
        ttt.insert(s[i]);
        c += s[i]-'a';
        c %= 3;
    }
    if(ttt.size()==1){
        cout << 1 << endl;
        return 0;
    }
    rep(i,n){
        if(i==0){
            dp[0][0][0][0] = 1;
            dp[0][1][1][0] = 1;
            dp[0][2][2][0] = 1;
        }else{
            rep(l,3){
                rep(k,3){
                    rep(j,3){
                        if(l!=k)dp[i][(j+k)%3][k][0] += dp[i-1][j][l][0];
                        else dp[i][(j+k)%3][k][1] += dp[i-1][j][l][0];
                        dp[i][(j+k)%3][k][1] += dp[i-1][j][l][1];
                        dp[i][(j+k)%3][k][0] %= mod;
                        dp[i][(j+k)%3][k][1] %= mod;

                    }
                }
            }
        }
    }
    ll ans = (dp[n-1][c][0][1]+dp[n-1][c][1][1]+dp[n-1][c][2][1])%mod;
    if(flag)ans++;
    ans %= mod;
    cout << ans << endl;
    return 0;
}
### Prompt

Develop a solution in Cpp to the problem described below:

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 <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <utility>
#include <queue>
#include <set>
#include <map>
#include <deque>
#include <iomanip>
#include <cstdio>
#include <stack>
#include <numeric>

using namespace std;
typedef  long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define  MP make_pair
#define  PB push_back
#define inf 1000000007
#define mod 998244353
#define rep(i,n) for(int i=0;i<(int)(n);++i)
set<string> st;int n;
char ch[]={'a','b','c'};
void dfs(string s){
    rep(i,n-1){
        if(s[i]!=s[i+1]){
            int c;
            rep(k,3){
                if(s[i]!=ch[k]&&s[i+1]!=ch[k]){
                    c = k;
                }
            }
            string t = s;
            t[i] = ch[c];
            t[i+1] = ch[c];
            if(st.count(t)==0){
                st.insert(t);
                dfs(t);
            }
        }
    }


}
ll dp[200010][3][3][2];
int main(){
    string s;
    cin >> s;
    n = s.size();
    if(n<=5){
        st.insert(s);
        dfs(s);
        for(auto x:st){
            cerr << x << endl;
        }
        cout << st.size() << endl;
        return 0;
    }
    set<char>ttt;
    int c = 0;
    bool flag = 1;
    rep(i,n-1){
        if(s[i]==s[i+1])flag = 0;
    }
    rep(i,n){
        ttt.insert(s[i]);
        c += s[i]-'a';
        c %= 3;
    }
    if(ttt.size()==1){
        cout << 1 << endl;
        return 0;
    }
    rep(i,n){
        if(i==0){
            dp[0][0][0][0] = 1;
            dp[0][1][1][0] = 1;
            dp[0][2][2][0] = 1;
        }else{
            rep(l,3){
                rep(k,3){
                    rep(j,3){
                        if(l!=k)dp[i][(j+k)%3][k][0] += dp[i-1][j][l][0];
                        else dp[i][(j+k)%3][k][1] += dp[i-1][j][l][0];
                        dp[i][(j+k)%3][k][1] += dp[i-1][j][l][1];
                        dp[i][(j+k)%3][k][0] %= mod;
                        dp[i][(j+k)%3][k][1] %= mod;

                    }
                }
            }
        }
    }
    ll ans = (dp[n-1][c][0][1]+dp[n-1][c][1][1]+dp[n-1][c][2][1])%mod;
    if(flag)ans++;
    ans %= mod;
    cout << ans << endl;
    return 0;
}
```