#define _USE_MATH_DEFINES
#include "bits/stdc++.h"
using namespace std;

#define int long long
typedef pair<int, int> P;

int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

/*
#define cin ifs
#define cout ofs
ifstream ifs("in.txt");
ofstream ofs("out.txt");
//*/

string S;
int ap[3];
int kind = 0;
int sum = 0;
int mod = 998244353;
int dp[220000][5][5];

int solve() {
    if (kind == 3) return 3;
    if (S[0] == S[2]) return 7;
    return 6;
}

signed main() {
    cin >> S;
    bool flag = false;
    for (int i = 0; i < S.length(); i++) {
        int k = S[i] - 'a';
        (sum += k) %= 3;
        if (!ap[k]) {
            kind++;
            ap[k] = true;
        }
    }
    for (int i = 1; i < S.length(); i++) {
        flag |= S[i] == S[i - 1];
    }
    if (kind == 1) {
        cout << 1 << endl;
        return 0;
    }

    if (S.length() == 3) {
        cout << solve() << endl;
        return 0;
    }
    int three = 1;
    for (int i = 1; i < S.length(); i++) {
        (three *= 3) %= mod;
    }
    dp[0][0][0] = 1, dp[0][1][1] = 1, dp[0][2][2] = 1;
    for (int i = 1; i < S.length(); i++) {
        dp[i][0][0] = (dp[i - 1][1][0] + dp[i - 1][2][0]) % mod;
        dp[i][0][1] = (dp[i - 1][1][2] + dp[i - 1][2][2]) % mod;
        dp[i][0][2] = (dp[i - 1][1][1] + dp[i - 1][2][1]) % mod;
        dp[i][1][0] = (dp[i - 1][0][2] + dp[i - 1][2][2]) % mod;
        dp[i][1][1] = (dp[i - 1][0][0] + dp[i - 1][2][0]) % mod;
        dp[i][1][2] = (dp[i - 1][0][1] + dp[i - 1][2][1]) % mod;
        dp[i][2][0] = (dp[i - 1][0][1] + dp[i - 1][1][1]) % mod;
        dp[i][2][1] = (dp[i - 1][0][2] + dp[i - 1][1][2]) % mod;
        dp[i][2][2] = (dp[i - 1][0][0] + dp[i - 1][1][0]) % mod;
    }
    int hik = (dp[S.length() - 1][0][sum] + dp[S.length() - 1][1][sum] + dp[S.length() - 1][2][sum]) % mod;
    int ans = (three - hik + mod + !flag) % 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
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"
using namespace std;

#define int long long
typedef pair<int, int> P;

int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

/*
#define cin ifs
#define cout ofs
ifstream ifs("in.txt");
ofstream ofs("out.txt");
//*/

string S;
int ap[3];
int kind = 0;
int sum = 0;
int mod = 998244353;
int dp[220000][5][5];

int solve() {
    if (kind == 3) return 3;
    if (S[0] == S[2]) return 7;
    return 6;
}

signed main() {
    cin >> S;
    bool flag = false;
    for (int i = 0; i < S.length(); i++) {
        int k = S[i] - 'a';
        (sum += k) %= 3;
        if (!ap[k]) {
            kind++;
            ap[k] = true;
        }
    }
    for (int i = 1; i < S.length(); i++) {
        flag |= S[i] == S[i - 1];
    }
    if (kind == 1) {
        cout << 1 << endl;
        return 0;
    }

    if (S.length() == 3) {
        cout << solve() << endl;
        return 0;
    }
    int three = 1;
    for (int i = 1; i < S.length(); i++) {
        (three *= 3) %= mod;
    }
    dp[0][0][0] = 1, dp[0][1][1] = 1, dp[0][2][2] = 1;
    for (int i = 1; i < S.length(); i++) {
        dp[i][0][0] = (dp[i - 1][1][0] + dp[i - 1][2][0]) % mod;
        dp[i][0][1] = (dp[i - 1][1][2] + dp[i - 1][2][2]) % mod;
        dp[i][0][2] = (dp[i - 1][1][1] + dp[i - 1][2][1]) % mod;
        dp[i][1][0] = (dp[i - 1][0][2] + dp[i - 1][2][2]) % mod;
        dp[i][1][1] = (dp[i - 1][0][0] + dp[i - 1][2][0]) % mod;
        dp[i][1][2] = (dp[i - 1][0][1] + dp[i - 1][2][1]) % mod;
        dp[i][2][0] = (dp[i - 1][0][1] + dp[i - 1][1][1]) % mod;
        dp[i][2][1] = (dp[i - 1][0][2] + dp[i - 1][1][2]) % mod;
        dp[i][2][2] = (dp[i - 1][0][0] + dp[i - 1][1][0]) % mod;
    }
    int hik = (dp[S.length() - 1][0][sum] + dp[S.length() - 1][1][sum] + dp[S.length() - 1][2][sum]) % mod;
    int ans = (three - hik + mod + !flag) % mod;
    cout << ans << endl;
    return 0;
}
```