#include<bits/stdc++.h>
#define X first
#define Y second
#define pb emplace_back
#define FOR(i,a,b) for(int (i)=(a);i<(b);++(i))
#define EFOR(i,a,b) for(int (i)=(a);i<=(b);++(i))
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define reps(X,S,Y) for (int (X) = S;(X) < (Y);++(X))
#define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X))
#define rreps(X,S,Y) for (int (X) = (Y)-1;(X) >= (S);--(X))
#define all(X) (X).begin(),(X).end()
#define rall(X) (X).rbegin(),(X).rend()
#define eb emplace_back
#define UNIQUE(X) (X).erase(unique(all(X)),(X).end())

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef ll LL;
typedef pii PII;
typedef pll PLL;
template<class T> using vv=vector<vector<T>>;
template<class T> inline bool MX(T &l,const T &r){return l<r?l=r,1:0;}
template<class T> inline bool MN(T &l,const T &r){return l>r?l=r,1:0;}
const ll MOD=998244353;

int N;
char buf[214514];
LL thr = 1;
LL two = 1;
LL dp[214514][3][3];
LL tot[3];

int main(){
  scanf("%s", buf);
  N = strlen(buf);

  bool adj = false;
  set<char> sig;
  rep(i, N-1) {
    adj |= (buf[i] == buf[i+1]);
    thr = thr * 3 % MOD;
    two = two * 2 % MOD;
  }

  int mod = 0;
  rep(i, N) {
    sig.insert(buf[i]);
    mod = (mod + buf[i] - 'a') % 3;
  }

  rep(i, 3) {
    dp[0][i][i] = 1;
  }

  reps(i, 1, N) {
    rep(j, 3) { // mod
      rep(k, 3) { // last
        rep(l, 3) { // c
          if (k == l) continue;
          int nm = (j+l) % 3;
          dp[i][nm][l] = (dp[i][nm][l] + dp[i-1][j][k]) % MOD;
        }
      }
    }
  }

  if (sig.size() == 1) {
    puts("1");
    return 0;
  }

  if (N == 3 && sig.size() == 3) {
    puts("3");
    return 0;
  }

  rep (i, 3) {
    rep(j, 3) {
      tot[i] = (tot[i] + dp[N-1][i][j]) % MOD;
    }
  }

  /*rep(i, 3) {
    printf("dp[%d]: %lld\n", i, tot[i]);
  }*/

  if (N%3/* || N == 3*/) {
    printf("%lld\n", (MOD+(thr-two+!adj)%MOD)%MOD);
  } else if (mod == 0) {
    if (!adj) {
      printf("%lld\n", (MOD+(1+thr-tot[mod])%MOD) % MOD);
    } else {
      printf("%lld\n", (MOD+(thr-tot[mod])%MOD) % MOD);
    }
  } else {
    if (!adj) {
      printf("%lld\n", (MOD+(1+thr-tot[mod])%MOD) % MOD);
    } else {
      printf("%lld\n", (MOD+(thr-tot[mod])%MOD) % MOD);
    }
  }
}

### 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 X first
#define Y second
#define pb emplace_back
#define FOR(i,a,b) for(int (i)=(a);i<(b);++(i))
#define EFOR(i,a,b) for(int (i)=(a);i<=(b);++(i))
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define reps(X,S,Y) for (int (X) = S;(X) < (Y);++(X))
#define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X))
#define rreps(X,S,Y) for (int (X) = (Y)-1;(X) >= (S);--(X))
#define all(X) (X).begin(),(X).end()
#define rall(X) (X).rbegin(),(X).rend()
#define eb emplace_back
#define UNIQUE(X) (X).erase(unique(all(X)),(X).end())

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef ll LL;
typedef pii PII;
typedef pll PLL;
template<class T> using vv=vector<vector<T>>;
template<class T> inline bool MX(T &l,const T &r){return l<r?l=r,1:0;}
template<class T> inline bool MN(T &l,const T &r){return l>r?l=r,1:0;}
const ll MOD=998244353;

int N;
char buf[214514];
LL thr = 1;
LL two = 1;
LL dp[214514][3][3];
LL tot[3];

int main(){
  scanf("%s", buf);
  N = strlen(buf);

  bool adj = false;
  set<char> sig;
  rep(i, N-1) {
    adj |= (buf[i] == buf[i+1]);
    thr = thr * 3 % MOD;
    two = two * 2 % MOD;
  }

  int mod = 0;
  rep(i, N) {
    sig.insert(buf[i]);
    mod = (mod + buf[i] - 'a') % 3;
  }

  rep(i, 3) {
    dp[0][i][i] = 1;
  }

  reps(i, 1, N) {
    rep(j, 3) { // mod
      rep(k, 3) { // last
        rep(l, 3) { // c
          if (k == l) continue;
          int nm = (j+l) % 3;
          dp[i][nm][l] = (dp[i][nm][l] + dp[i-1][j][k]) % MOD;
        }
      }
    }
  }

  if (sig.size() == 1) {
    puts("1");
    return 0;
  }

  if (N == 3 && sig.size() == 3) {
    puts("3");
    return 0;
  }

  rep (i, 3) {
    rep(j, 3) {
      tot[i] = (tot[i] + dp[N-1][i][j]) % MOD;
    }
  }

  /*rep(i, 3) {
    printf("dp[%d]: %lld\n", i, tot[i]);
  }*/

  if (N%3/* || N == 3*/) {
    printf("%lld\n", (MOD+(thr-two+!adj)%MOD)%MOD);
  } else if (mod == 0) {
    if (!adj) {
      printf("%lld\n", (MOD+(1+thr-tot[mod])%MOD) % MOD);
    } else {
      printf("%lld\n", (MOD+(thr-tot[mod])%MOD) % MOD);
    }
  } else {
    if (!adj) {
      printf("%lld\n", (MOD+(1+thr-tot[mod])%MOD) % MOD);
    } else {
      printf("%lld\n", (MOD+(thr-tot[mod])%MOD) % MOD);
    }
  }
}

```