#include <bits/stdc++.h>
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(x) begin(x),end(x)

using namespace std;
using ll = int64_t;
constexpr ll MOD = 998244353;

ll calc(const string& s) {
  ll m = 0;
  for (char c : s) {
    m += c - 'a';
    m %= 3;
  }
  return m;
}

int main() {
  string s;
  cin>>s;
  int n = s.size();
  if (n < 4) {
    set<string> t;
    t.insert(s);
    queue<string> q;
    q.push(s);
    while (!q.empty()) {
      string tmp = q.front();
      q.pop();
      REP(i,n-1) {
        if (tmp[i] != tmp[i+1]) {
          int sum = 3;
          sum -= (tmp[i] - 'a') + (tmp[i+1] - 'a');
          string next = tmp;
          next[i] = sum + 'a';
          next[i+1] = sum + 'a';
          if (t.count(next) == 0) {
            t.insert(next);
            q.push(next);
          }
        }
      }
    }
    cout << t.size() << endl;
    return 0;
  }
  vector<vector<vector<ll>>> dp(n+1, vector<vector<ll>>(3, vector<ll>(3, 0)));
  dp[0][0][0] = 1;
  REP(i,n) {
    REP(j,3)REP(k,3) {
      REP(c,3) {
        if (i!=0 && c==k) continue;
        dp[i+1][(j+c)%3][c] += dp[i][j][k];
        dp[i+1][(j+c)%3][c] %= MOD;
      }
    }
  }
  ll m = calc(s);
  ll sum = 0;
  REP(i,3) sum += dp[n][m][i];
  sum %= MOD;
  ll pm = 1;
  REP(i,n-1) {
    pm *= 3;
    pm %= MOD;
  }
  ll ans = pm - sum;
  if (ans < 0) ans += MOD;
  bool diff = true;
  bool same = true;
  REP(i,n-1) {
    if (s[i] == s[i+1]) diff = false;
    else same = false;
  }
  if (diff) {
    ans += 1;
    ans %= MOD;
  }
  if (same) {
    ans = 1;
  }
  cout << ans << endl;
  return 0;
}

### Prompt

Please formulate 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 FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(x) begin(x),end(x)

using namespace std;
using ll = int64_t;
constexpr ll MOD = 998244353;

ll calc(const string& s) {
  ll m = 0;
  for (char c : s) {
    m += c - 'a';
    m %= 3;
  }
  return m;
}

int main() {
  string s;
  cin>>s;
  int n = s.size();
  if (n < 4) {
    set<string> t;
    t.insert(s);
    queue<string> q;
    q.push(s);
    while (!q.empty()) {
      string tmp = q.front();
      q.pop();
      REP(i,n-1) {
        if (tmp[i] != tmp[i+1]) {
          int sum = 3;
          sum -= (tmp[i] - 'a') + (tmp[i+1] - 'a');
          string next = tmp;
          next[i] = sum + 'a';
          next[i+1] = sum + 'a';
          if (t.count(next) == 0) {
            t.insert(next);
            q.push(next);
          }
        }
      }
    }
    cout << t.size() << endl;
    return 0;
  }
  vector<vector<vector<ll>>> dp(n+1, vector<vector<ll>>(3, vector<ll>(3, 0)));
  dp[0][0][0] = 1;
  REP(i,n) {
    REP(j,3)REP(k,3) {
      REP(c,3) {
        if (i!=0 && c==k) continue;
        dp[i+1][(j+c)%3][c] += dp[i][j][k];
        dp[i+1][(j+c)%3][c] %= MOD;
      }
    }
  }
  ll m = calc(s);
  ll sum = 0;
  REP(i,3) sum += dp[n][m][i];
  sum %= MOD;
  ll pm = 1;
  REP(i,n-1) {
    pm *= 3;
    pm %= MOD;
  }
  ll ans = pm - sum;
  if (ans < 0) ans += MOD;
  bool diff = true;
  bool same = true;
  REP(i,n-1) {
    if (s[i] == s[i+1]) diff = false;
    else same = false;
  }
  if (diff) {
    ans += 1;
    ans %= MOD;
  }
  if (same) {
    ans = 1;
  }
  cout << ans << endl;
  return 0;
}

```