#include <cassert>
#include <queue>
#include <set>
#include <cstring>
#include <numeric>
#include <iostream>
using namespace std;

bool alleq(string &s) {
    for (int i = 1; i < s.size(); i++) if (s[0] != s[i]) return false;
    return true;
}

bool checkadj(string &s) {
    for (int i = 1; i < s.size(); i++) if (s[i-1] == s[i]) return true;
    return false;
}

const int M = 998244353;

long long modexp(int x, long long e, int m) {
    long long ans = 1, p = x % m;
    while (e > 0) {
        if (e % 2 != 0) ans = (ans * p) % m;
        p = (p * p) % m;
        e >>= 1;
    }
    return ans;
}

int bruteforce(string &s) {
    set<string> ss;
    ss.insert(s);
    queue<string> q;
    q.push(s);
    int ans = 0;
    while (!q.empty()) {
        string t = q.front();
        q.pop();
        ans++;
        for (int i = 1; i < t.size(); i++) {
            if (t[i-1] != t[i]) {
                char c = int('a') + 'b' + 'c' - t[i-1] - t[i];
                string u = t;
                u[i-1] = u[i] = c;
                if (ss.find(u) == ss.end()) {
                    ss.insert(u);
                    q.push(u);
                }
            }
        }
    }
    return ans;
}

int main() {
    string s; cin >> s;
    if (alleq(s)) {
        assert (bruteforce(s) == 1);
        cout << "1\n";
        return 0;
    }
    if (s.size() == 3 && s[0] != s[1] && s[1] != s[2] && s[2] != s[0]) {
        assert (bruteforce(s) == 3);
        cout << "3\n";
        return 0;
    }

    int dp[2][3][3] = {}, cur = 0, prev = 1;
    for (int j = 0; j < 3; j++) dp[prev][j][j] = 1;
    for (int i = 1; i < s.size(); i++) {
        memset(dp[cur], 0, sizeof(dp[cur]));
        for (int j = 0; j < 3; j++)
            for (int k = 0; k < 3; k++)
                for (int l = 0; l < 3; l++)
                    if (k != l) dp[cur][(j + l)%3][l] += dp[prev][j][k] % M;

        swap(prev, cur);
    }
    const int sum = accumulate(s.begin(), s.end(), 0) % 3;
    long long ans = modexp(3, s.size()-1, M);
    ans -= accumulate(dp[prev][sum], dp[prev][sum]+3, 0LL);
    if (!checkadj(s)) ans++;
    cout << (ans % M + M) % M << endl;
}
//     int ans2 = bruteforce(s);
//     if ((ans2 - ans) % M != 0)
//         cerr << "NG: " << s << " " << ans2 << endl;
//     else cerr << "OK\n";
// }

### Prompt

Construct a cpp code solution to the problem outlined:

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 <cassert>
#include <queue>
#include <set>
#include <cstring>
#include <numeric>
#include <iostream>
using namespace std;

bool alleq(string &s) {
    for (int i = 1; i < s.size(); i++) if (s[0] != s[i]) return false;
    return true;
}

bool checkadj(string &s) {
    for (int i = 1; i < s.size(); i++) if (s[i-1] == s[i]) return true;
    return false;
}

const int M = 998244353;

long long modexp(int x, long long e, int m) {
    long long ans = 1, p = x % m;
    while (e > 0) {
        if (e % 2 != 0) ans = (ans * p) % m;
        p = (p * p) % m;
        e >>= 1;
    }
    return ans;
}

int bruteforce(string &s) {
    set<string> ss;
    ss.insert(s);
    queue<string> q;
    q.push(s);
    int ans = 0;
    while (!q.empty()) {
        string t = q.front();
        q.pop();
        ans++;
        for (int i = 1; i < t.size(); i++) {
            if (t[i-1] != t[i]) {
                char c = int('a') + 'b' + 'c' - t[i-1] - t[i];
                string u = t;
                u[i-1] = u[i] = c;
                if (ss.find(u) == ss.end()) {
                    ss.insert(u);
                    q.push(u);
                }
            }
        }
    }
    return ans;
}

int main() {
    string s; cin >> s;
    if (alleq(s)) {
        assert (bruteforce(s) == 1);
        cout << "1\n";
        return 0;
    }
    if (s.size() == 3 && s[0] != s[1] && s[1] != s[2] && s[2] != s[0]) {
        assert (bruteforce(s) == 3);
        cout << "3\n";
        return 0;
    }

    int dp[2][3][3] = {}, cur = 0, prev = 1;
    for (int j = 0; j < 3; j++) dp[prev][j][j] = 1;
    for (int i = 1; i < s.size(); i++) {
        memset(dp[cur], 0, sizeof(dp[cur]));
        for (int j = 0; j < 3; j++)
            for (int k = 0; k < 3; k++)
                for (int l = 0; l < 3; l++)
                    if (k != l) dp[cur][(j + l)%3][l] += dp[prev][j][k] % M;

        swap(prev, cur);
    }
    const int sum = accumulate(s.begin(), s.end(), 0) % 3;
    long long ans = modexp(3, s.size()-1, M);
    ans -= accumulate(dp[prev][sum], dp[prev][sum]+3, 0LL);
    if (!checkadj(s)) ans++;
    cout << (ans % M + M) % M << endl;
}
//     int ans2 = bruteforce(s);
//     if ((ans2 - ans) % M != 0)
//         cerr << "NG: " << s << " " << ans2 << endl;
//     else cerr << "OK\n";
// }

```