#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef vector<VI> VVI;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

int naive(string s){
    int n = s.length();
    queue<string> que;
    que.push(s);
    set<string> st;
    st.insert(s);
    while (!que.empty()){
        string t = que.front();
        que.pop();
        REP(i,n-1){
            if (t[i] != t[i+1]){
                string u = t;
                string sub = t.substr(i, 2);
                if (sub == "ab" || sub == "ba"){
                    u[i] = u[i+1] = 'c';
                }else if (sub == "bc" || sub == "cb"){
                    u[i] = u[i+1] = 'a';
                }else{
                    u[i] = u[i+1] = 'b';
                }

                if (st.count(u) == 0){
                    st.insert(u);
                    que.push(u);
                }
            }
        }
    }

    return st.size();
}

ll dp[200010][3][3][2];
const ll mod = 998244353;

int main() {
    string s;
    cin >> s;
    int n = s.length();

    bool same = true;
    REP(i,n) if (s[0] != s[i]) same = false;

    if (same){
        cout << 1 << endl;
        return 0;
    }

    if (n <= 10){
        cout << naive(s) << endl;
        return 0;
    }

    int m = 0;
    REP(i,n) m = (m + s[i] - 'a') % 3;

    REP(i,3) dp[0][i][i][0] = 1;

    REP(i,n-1) REP(j,3) REP(p,3) REP(k,2){
        REP(l,3){
            (dp[i+1][(j+l)%3][l][k|(p==l)] += dp[i][j][p][k]) %= mod;
        }
    }

    ll ans = 0;
    REP(j,3) ans = (ans + dp[n-1][m][j][1]) % mod;

    bool dif = true;
    REP(i,n-1) if (s[i] == s[i+1]) dif = false;

    if (dif) 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 <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef vector<VI> VVI;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

int naive(string s){
    int n = s.length();
    queue<string> que;
    que.push(s);
    set<string> st;
    st.insert(s);
    while (!que.empty()){
        string t = que.front();
        que.pop();
        REP(i,n-1){
            if (t[i] != t[i+1]){
                string u = t;
                string sub = t.substr(i, 2);
                if (sub == "ab" || sub == "ba"){
                    u[i] = u[i+1] = 'c';
                }else if (sub == "bc" || sub == "cb"){
                    u[i] = u[i+1] = 'a';
                }else{
                    u[i] = u[i+1] = 'b';
                }

                if (st.count(u) == 0){
                    st.insert(u);
                    que.push(u);
                }
            }
        }
    }

    return st.size();
}

ll dp[200010][3][3][2];
const ll mod = 998244353;

int main() {
    string s;
    cin >> s;
    int n = s.length();

    bool same = true;
    REP(i,n) if (s[0] != s[i]) same = false;

    if (same){
        cout << 1 << endl;
        return 0;
    }

    if (n <= 10){
        cout << naive(s) << endl;
        return 0;
    }

    int m = 0;
    REP(i,n) m = (m + s[i] - 'a') % 3;

    REP(i,3) dp[0][i][i][0] = 1;

    REP(i,n-1) REP(j,3) REP(p,3) REP(k,2){
        REP(l,3){
            (dp[i+1][(j+l)%3][l][k|(p==l)] += dp[i][j][p][k]) %= mod;
        }
    }

    ll ans = 0;
    REP(j,3) ans = (ans + dp[n-1][m][j][1]) % mod;

    bool dif = true;
    REP(i,n-1) if (s[i] == s[i+1]) dif = false;

    if (dif) ans = (ans + 1) % mod;
    cout << ans << endl;

    return 0;
}

```