#include<cstdio>
#include<cstring>
using namespace std;
typedef long long int LL;
const int MAXN = 201010;
const int mod = 998244353;
char ch[MAXN];
LL dp[4][4], roll[4][4];
int sum, flag = 1;

LL x = 1, y, ans = 1;
int main(){
    scanf("%s", ch);
    for(int i = 0; ch[i]; i ++){
        sum += ch[i] - 'a',sum %= 3;
        if(ch[i] != ch[0])
            flag = 0;
    }
    if(flag){
        printf("1");
        return 0;
    }
    else if(strlen(ch) == 3){
        if(ch[0] == ch[2])
            ans = 7;
        int cnt = 0;
        if(ch[0] != ch[1])
            cnt ++;
        if(ch[2] != ch[1])
            cnt ++;
        if(ch[0] != ch[2])
            cnt ++;
        if(cnt == 3){
            ans = 3;
        }
        if(ans != 7 && cnt == 2){
            ans = 6;
        }
        printf("%d", ans);
        return 0;
    }
    dp[0][0] = dp[1][1] = dp[2][2] = 1;
    for(int i = 1; ch[i]; i ++){
        for(int j = 0; j < 3; j ++){
            for(int k = 0; k < 3; k ++){
                for(int p = 0; p < 3; p ++){
                    if(k == p)
                        continue;
                    roll[(j+p)%3][p] += dp[j][k];
                }
            }
        }
        for(int j = 0; j < 3; j ++){
            for(int k = 0; k < 3; k ++){
                dp[j][k] = roll[j][k] % mod;
                roll[j][k] = 0;
            }
        }
    }
    for(int i = 1; ch[i]; i ++){
        x *= 3;
        x %= mod;
        if(ch[i] == ch[i-1])
            ans = 0;
    }
    for(int i = 0; i < 3; i ++){
        y += dp[sum][i];
        y %= mod;
    }
    ans += x - y + mod;
    ans %= mod;
    printf("%lld", ans);
}

### Prompt

Create a solution in cpp for 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<cstdio>
#include<cstring>
using namespace std;
typedef long long int LL;
const int MAXN = 201010;
const int mod = 998244353;
char ch[MAXN];
LL dp[4][4], roll[4][4];
int sum, flag = 1;

LL x = 1, y, ans = 1;
int main(){
    scanf("%s", ch);
    for(int i = 0; ch[i]; i ++){
        sum += ch[i] - 'a',sum %= 3;
        if(ch[i] != ch[0])
            flag = 0;
    }
    if(flag){
        printf("1");
        return 0;
    }
    else if(strlen(ch) == 3){
        if(ch[0] == ch[2])
            ans = 7;
        int cnt = 0;
        if(ch[0] != ch[1])
            cnt ++;
        if(ch[2] != ch[1])
            cnt ++;
        if(ch[0] != ch[2])
            cnt ++;
        if(cnt == 3){
            ans = 3;
        }
        if(ans != 7 && cnt == 2){
            ans = 6;
        }
        printf("%d", ans);
        return 0;
    }
    dp[0][0] = dp[1][1] = dp[2][2] = 1;
    for(int i = 1; ch[i]; i ++){
        for(int j = 0; j < 3; j ++){
            for(int k = 0; k < 3; k ++){
                for(int p = 0; p < 3; p ++){
                    if(k == p)
                        continue;
                    roll[(j+p)%3][p] += dp[j][k];
                }
            }
        }
        for(int j = 0; j < 3; j ++){
            for(int k = 0; k < 3; k ++){
                dp[j][k] = roll[j][k] % mod;
                roll[j][k] = 0;
            }
        }
    }
    for(int i = 1; ch[i]; i ++){
        x *= 3;
        x %= mod;
        if(ch[i] == ch[i-1])
            ans = 0;
    }
    for(int i = 0; i < 3; i ++){
        y += dp[sum][i];
        y %= mod;
    }
    ans += x - y + mod;
    ans %= mod;
    printf("%lld", ans);
}

```