Problem:
 Score : 700 points    Problem Statement 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 .        Sample Input 1 abc      Sample Output 1 3  abc , aaa and ccc can be obtained.       Sample Input 2 abbac      Sample Output 2 65       Sample Input 3 babacabac      Sample Output 3 6310       Sample Input 4 ababacbcacbacacbcbbcbbacbaccacbacbacba      Sample Output 4 148010497

Solution (Python):
s = input()
n = len(s)
flg = 0
for i in range(1,n):
  if s[i-1] != s[i]:
    flg += 1
if flg == 0:
  print(1)
  exit()
par = (s.count("a")+s.count("b")*2+2)%3
dp = [[0 for i in range(9)] for j in range(n)]
mod = 998244353
dp[0][0] = 1
dp[0][4] = 1
dp[0][8] = 1
for i in range(1,n):
  dp[i][0] = dp[i-1][5]+dp[i-1][8]
  dp[i][1] = dp[i-1][3]+dp[i-1][6]
  dp[i][2] = dp[i-1][4]+dp[i-1][7]
  dp[i][3] = dp[i-1][1]+dp[i-1][7]
  dp[i][4] = dp[i-1][2]+dp[i-1][8]
  dp[i][5] = dp[i-1][0]+dp[i-1][6]
  dp[i][6] = dp[i-1][0]+dp[i-1][3]
  dp[i][7] = dp[i-1][1]+dp[i-1][4]
  dp[i][8] = dp[i-1][2]+dp[i-1][5]
  for j in range(9):
    dp[i][j] %= mod
ans = pow(3,n-1,mod)-dp[-1][par]-dp[-1][par+3]-dp[-1][par+6]
if flg == n-1:
  ans += 1
if n == 3 and flg == n-1 and par == 2:
  ans -= 1
print(ans%mod)

Solution (Python):
def main():
    md = 998244353
    s = input()
    n = len(s)
    al = True  
    an = 1  
    for c0, c1 in zip(s, s[1:]):
        if c0 == c1:
            an = 0
        else:
            al = False
        if an == 0 and not al: break
    if al:
        print(1)
        exit()
    if n == 2:
        print(2)
        exit()
    if n == 3:
        if s[0] == s[-1]:
            print(7)
        elif s[0] == s[1] or s[1] == s[2]:
            print(6)
        else:
            print(3)
        exit()
    
    
    ord0=ord("a")
    r = sum(ord(c) - ord0 for c in s) % 3
    if n%3==0:
        d=pow(2,n//3-1,md)
        if r==0:
            an-=d*2
        else:
            an+=d
    print((pow(3, n - 1, md) - pow(2, n - 1, md) + an) % md)

main()

Solution (Python):
def main():
    md = 998244353
    s = input()
    n = len(s)
    if s.count(s[0]) == n:
        print(1)
        exit()
    if n == 2:
        print(2)
        exit()
    if n == 3:
        if s[0] == s[-1]:
            print(7)
        elif s[0] == s[1] or s[1] == s[2]:
            print(6)
        else:
            print(3)
        exit()
    ord0 = ord("a")
    a = [ord(c) - ord0 for c in s]
    r = sum(a) % 3
    dp = [[[[0] * 3 for _ in range(2)] for _ in range(3)] for _ in range(n)]
    for m in range(3):
        dp[0][m][0][m] = 1
    
    
    for i in range(n - 1):
        for j in range(3):
            for k in range(2):
                for m in range(3):
                    pre = dp[i][j][k][m]  
                    for nm in range(3):
                        nj = (j + nm) % 3
                        if nm == m:
                            dp[i + 1][nj][1][nm] = (dp[i + 1][nj][1][nm] + pre) % md
                        else:
                            dp[i + 1][nj][k][nm] = (dp[i + 1][nj][k][nm] + pre) % md
    d = 1
    for c0, c1 in zip(s, s[1:]):
        if c0 == c1:
            d = 0
            break
    print((sum(dp[n - 1][r][1]) + d) % md)

main()

Solution (Python):
import sys
input = sys.stdin.readline

import numpy as np

MOD = 998244353

S = input().rstrip()

arr = np.array(list(S.replace('a','0').replace('b','1').replace('c','2')),dtype=np.int32)

if (arr == arr[0]).all():
    print(1)
    exit()

def solve_naive(S):
    se = set([S])
    q = [S]
    while q:
        S = q.pop()
        for i in range(len(S)-1):
            x,y = S[i:i+2]
            if x == y:
                continue
            for t in 'abc':
                if t != x and t != y:
                    T = S[:i] + t+t + S[i+2:]
                    if T not in se:
                        q.append(T)
                        se.add(T)
    return len(se)

LS = len(S)
if LS < 6:
    answer = solve_naive(S)
    print(answer)
    exit()



answer = pow(3,LS-1,MOD)

if LS%3 == 0:
    x,y = (3+MOD)//2,0
    for _ in range(LS//3):
        x,y = 4*x+4*y,2*x+6*y
        x %= MOD
        y %= MOD
    if arr.sum()%3 == 0:
        answer -= x
    else:
        answer -= y
else:
    answer -= pow(2,LS-1,MOD)

if (arr[:-1] != arr[1:]).all():
    answer += 1

answer %= MOD
print(answer)

Solution (Python):
from collections import defaultdict
import sys
S=input()
N=len(S)
if N==3:
    if S[0]==S[1]:
        if S[1]==S[2]:
            print(1)
        else:
            print(6)
    else:
        if S[0]==S[2]:
            print(7)
        elif S[1]==S[2]:
            print(6)
        else:
            print(3)
    sys.exit()
a=S[0]
t=1
for i in range(N):
    if S[i]!=a:
        t=0
        break
if t==1:
    print(1)
    sys.exit()

mod=998244353
M=0
for s in S:
    if s=='b':
        M+=1
    elif s=='c':
        M+=2
    M%=3
dp=[]
for i in range(2):
    for k in range(3):
        for l in range(3):
            dp.append((i,k,l))
dd=[[[0]*3 for i in range(3)] for i in range(2)]
for i in range(3):
    dd[0][i][i]=1
for k in range(2,N+1):
    nd=[[[0]*3 for i in range(3)] for i in range(2)]
    for p in dp:
        con,moji,m=p
        n=dd[con][moji][m]
        
        if con==0:
            for k in range(3):
                if moji==k:
                    nd[1][k][ (m + k) % 3] += n
                    nd[1] [k ][(m + k) % 3] %=mod
                else:
                    nd[0][k][(m+k)%3]+=n
                    nd[0][ k] [(m+k) % 3] %=mod
        else:
            for k in range(3):
                nd[1][k][(m + k) % 3] += n
                nd[1][k][(m + k) % 3] %=mod
    
    dd=nd
flag=1
for i in range(N-1):
    if S[i]==S[i+1]:
        flag=0
ans=flag
for k in range(3):
    ans+=dd[1][k][M]
    ans%=mod
print(ans)

Solution (Python):
s = list(input())

n = len(s)

a = [0] * n

MOD = 998244353

for i in range(n):
    a[i] = ord(s[i]) - ord('a')

if max(a) == min(a):
    print(1)
    exit()
elif n == 3:
    def solver(m):
        x = m // 100
        y = ( m % 100 ) // 10
        z = m % 10
        if x != y:
            c = (3 - x - y) % 3
            temp = c * 110 + z
            if temp not in ans:
                ans.add(temp)
                solver(temp)
        if y != z:
            c = (3 - y - z) % 3
            temp = x * 100 + c * 11
            if temp not in ans:
                ans.add(temp)
                solver(temp)

    t = a[0] * 100 + a[1] * 10 + a[2]
    ans = set()
    ans.add(t)
    solver(t)
    print(len(ans))
    exit()
elif n == 2:
    print(2)
    exit()

dp = [[0,0,0] for _ in range(3)]

dp[0][0] = 1
dp[1][1] = 1
dp[2][2] = 1

for i in range(n-1):
    T = [[0,0,0] for _ in range(3)]
    T[0][0] = (dp[1][0] + dp[2][0]) % MOD
    T[0][1] = (dp[1][1] + dp[2][1]) % MOD
    T[0][2] = (dp[1][2] + dp[2][2]) % MOD
    T[1][0] = (dp[0][2] + dp[2][2]) % MOD
    T[1][1] = (dp[0][0] + dp[2][0]) % MOD
    T[1][2] = (dp[0][1] + dp[2][1]) % MOD
    T[2][0] = (dp[0][1] + dp[1][1]) % MOD
    T[2][1] = (dp[0][2] + dp[1][2]) % MOD
    T[2][2] = (dp[0][0] + dp[1][0]) % MOD
    dp, T = T, dp

m = sum(a) % 3

ans = 3 ** (n-1) - (dp[0][m] + dp[1][m] + dp[2][m])

check = 1
for i in range(n-1):
    if a[i] == a[i+1]:
        check = 0
        break

ans += check



print(ans % MOD)

Solution (Python):
from collections import Counter
import sys
sys.setrecursionlimit(10**6)

MOD = 998244353

ABC = "abc".index
*S, = map(ABC, input())
N = len(S)

def bruteforce(S):
    used = set()
    def dfs(s):
        key = tuple(s)
        if key in used:
            return
        used.add(key)
        for i in range(len(s)-1):
            if s[i] != s[i+1]:
                a = s[i]; b = s[i+1]
                s[i] = s[i+1] = 3 - a - b
                dfs(s)
                s[i] = a; s[i+1] = b
    dfs(S)
    return len(used)

if len(S) <= 3:
    print(bruteforce(S))
else:
    c = Counter(S)
    if c[0] == N or c[1] == N or c[2] == N:
        print(1)
    else:
        P = [[[0,0] for i in range(3)] for j in range(3)]
        Q = [[[0,0] for i in range(3)] for j in range(3)]
        P[0][0][0] = P[1][1][0] = P[2][2][0] = 1
        for i in range(N-1):
            for p in range(3):
                for q in range(3):
                    for r in range(2):
                        Q[p][q][r] = 0
            for p in range(3):
                for q in range(3):
                    for r in range(2):
                        for k in range(3):
                            Q[k][(q+k)%3][r | (p == k)] += P[p][q][r] % MOD
            P, Q = Q, P
        ans = 0
        r = sum(S) % 3
        for i in range(3):
            ans += P[i][r][1]
        if all(S[i] != S[i+1] for i in range(N-1)):
            ans += 1
        print(ans % MOD)

Solution (Python):



M = 998244353

def powmod(a, x, m = M):
    y = 1
    while 0 < x:
        if x % 2 == 1:
            y *= a
            y %= m
        x //= 2
        a = a ** 2
        a %= m

    return y


def solve(s):
    n = len(s)

    nb = nc = 0
    ch = s[0]
    if ch == 'b':
        nb += 1
    elif ch == 'c':
        nc += 1
    sf = True
    tf = True
    left = ch
    for ch in s[1:]:
        if ch == 'b':
            nb += 1
        elif ch == 'c':
            nc += 1
        if ch == left:
            sf = False
        else:
            tf = False
        left = ch


    if tf:
        return 1
    if n == 3:
        if (nb + nc * 2) % 3:
            return 7 if sf else 6
        else:
            return 3
    if n % 3:
        return (powmod(3, n - 1) + M - powmod(2, n - 1) + (1 if sf else 0)) % M
    else:
        if (nb + nc * 2) % 3:
            return (powmod(3, n - 1) + M - (powmod(2, n - 1) - powmod(2, n // 3 - 1)) + (1 if sf else 0)) % M
        else:
            return (powmod(3, n - 1) + M - (powmod(2, n // 3) + 4 * powmod(8, n // 3 - 1)) + (1 if sf else 0)) % M

def main():
    s = input()

    print(solve(s))


if __name__ == '__main__':
    main()

Solution (Python):
def solve(s):
    if all(a == b for a, b in zip(s, s[1:])):
        return 1
    if len(s) == 2:
        return 2
    elif len(s) == 3:
        if s[0] == s[1] or s[1] == s[2]:
            return 6
        elif s[0] == s[2]:
            return 7
        else:
            return 3
    
    dp = [[[0] * 3 for _ in range(3)], [0] * 3]
    dp[0][0][0] = 1
    dp[0][1][1] = 1
    dp[0][2][2] = 1
    MOD = 998244353
    for _ in range(len(s) - 1):
        ndp = [[[0] * 3 for _ in range(3)], [0] * 3]
        dp0, dp1 = dp
        ndp0, ndp1 = ndp
        sdp1 = sum(dp1)
        ndp0[0][0] = (dp0[0][1] + dp0[0][2]) % MOD
        ndp0[1][0] = (dp0[1][1] + dp0[1][2]) % MOD
        ndp0[2][0] = (dp0[2][1] + dp0[2][2]) % MOD
        ndp0[0][1] = (dp0[2][0] + dp0[2][2]) % MOD
        ndp0[1][1] = (dp0[0][0] + dp0[0][2]) % MOD
        ndp0[2][1] = (dp0[1][0] + dp0[1][2]) % MOD
        ndp0[0][2] = (dp0[1][0] + dp0[1][1]) % MOD
        ndp0[1][2] = (dp0[2][0] + dp0[2][1]) % MOD
        ndp0[2][2] = (dp0[0][0] + dp0[0][1]) % MOD
        ndp1[0] = (dp0[0][0] + dp0[1][2] + dp0[2][1] + sdp1) % MOD
        ndp1[1] = (dp0[1][0] + dp0[2][2] + dp0[0][1] + sdp1) % MOD
        ndp1[2] = (dp0[2][0] + dp0[0][2] + dp0[1][1] + sdp1) % MOD
        dp = ndp
    return (dp[1][sum(map(ord, s)) % 3] + all(a != b for a, b in zip(s, s[1:]))) % MOD


s = input()
print(solve(s))

Solution (Python):
import itertools

S = input()
N = len(S)
if all(S[0] == c for c in S):
    print(1)
    exit()
if N == 2:
    print(1 if S[0]==S[1] else 2)
    exit()

if N == 3:
    def another(a,b):
        s = set('abc')
        s -= set([a,b])
        return list(s)[0]
    ptn = set()
    stack = [S]
    while stack:
        a = stack.pop()
        ptn.add(a)
        if a[0] != a[1]:
            b = another(a[0],a[1])*2 + a[2]
            if not b in ptn:
                stack.append(b)
        if a[1] != a[2]:
            c = a[0] + another(a[1],a[2])*2
            if not c in ptn:
                stack.append(c)
    print(len(ptn))
    exit()


MOD = 998244353
dp = [[[0 for u in range(2)] for l in range(3)] for s in range(3)]

for ptn in itertools.product(range(3),repeat=4):
    seq = (ptn[0]==ptn[1] or ptn[1]==ptn[2] or ptn[2]==ptn[3])
    dp[sum(ptn)%3][ptn[3]][seq] += 1

for n in range(4,N):
    dp2 = [[[0 for u in range(2)] for l in range(3)] for s in range(3)]
    for s in range(3):
        for l in range(3):
            for u in range(2):
                for l2 in range(3):
                    s2 = (s+l2)%3
                    u2 = u or l==l2
                    dp2[s2][l2][u2] += dp[s][l][u]
                    dp2[s2][l2][u2] %= MOD
    dp = dp2

sm = 0
for c in S:
    sm += ord(c) - ord('a')
seq = False
for c1,c2 in zip(S,S[1:]):
    if c1 == c2:
        seq = True
        break
ans = sum([dp[sm%3][i][1] for i in range(3)])
if not seq: ans += 1
print(ans % MOD)

Solution (Python):
def solve(s):
    if all(a == b for a, b in zip(s, s[1:])):
        return 1
    if len(s) == 2:
        return 2
    elif len(s) == 3:
        if s[0] == s[1] or s[1] == s[2]:
            return 6
        elif s[0] == s[2]:
            return 7
        else:
            return 3
    
    dp = [[[0] * 3 for _ in range(3)], [0] * 3]
    dp[0][0][0] = 1
    dp[0][1][1] = 1
    dp[0][2][2] = 1
    MOD = 998244353
    for _ in range(len(s) - 1):
        ndp = [[[0] * 3 for _ in range(3)], [0] * 3]
        dp0, dp1 = dp
        ndp0, ndp1 = ndp
        sdp1 = sum(dp1)
        ndp0[0][0] = (dp0[0][1] + dp0[0][2]) % MOD
        ndp0[1][0] = (dp0[1][1] + dp0[1][2]) % MOD
        ndp0[2][0] = (dp0[2][1] + dp0[2][2]) % MOD
        ndp0[0][1] = (dp0[2][0] + dp0[2][2]) % MOD
        ndp0[1][1] = (dp0[0][0] + dp0[0][2]) % MOD
        ndp0[2][1] = (dp0[1][0] + dp0[1][2]) % MOD
        ndp0[0][2] = (dp0[1][0] + dp0[1][1]) % MOD
        ndp0[1][2] = (dp0[2][0] + dp0[2][1]) % MOD
        ndp0[2][2] = (dp0[0][0] + dp0[0][1]) % MOD
        ndp1[0] = (dp0[0][0] + dp0[1][2] + dp0[2][1] + sdp1) % MOD
        ndp1[1] = (dp0[1][0] + dp0[2][2] + dp0[0][1] + sdp1) % MOD
        ndp1[2] = (dp0[2][0] + dp0[0][2] + dp0[1][1] + sdp1) % MOD
        dp = ndp
    return (dp[1][sum(map(ord, s)) % 3] + all(a != b for a, b in zip(s, s[1:]))) % MOD


s = input()
print(solve(s))

Solution (Python):
def solve(s):
    if all(a == b for a, b in zip(s, s[1:])):
        return 1
    if len(s) == 2:
        return 2
    elif len(s) == 3:
        if s[0] == s[1] or s[1] == s[2]:
            return 6
        elif s[0] == s[2]:
            return 7
        else:
            return 3
    
    dp = [[[0] * 3 for _ in range(3)], [0] * 3]
    dp[0][0][0] = 1
    dp[0][1][1] = 1
    dp[0][2][2] = 1
    MOD = 998244353
    for _ in range(len(s) - 1):
        ndp = [[[0] * 3 for _ in range(3)], [0] * 3]
        dp0, dp1 = dp
        ndp0, ndp1 = ndp
        sdp1 = sum(dp1)
        ndp0[0][0] = (dp0[0][1] + dp0[0][2]) % MOD
        ndp0[1][0] = (dp0[1][1] + dp0[1][2]) % MOD
        ndp0[2][0] = (dp0[2][1] + dp0[2][2]) % MOD
        ndp0[0][1] = (dp0[2][0] + dp0[2][2]) % MOD
        ndp0[1][1] = (dp0[0][0] + dp0[0][2]) % MOD
        ndp0[2][1] = (dp0[1][0] + dp0[1][2]) % MOD
        ndp0[0][2] = (dp0[1][0] + dp0[1][1]) % MOD
        ndp0[1][2] = (dp0[2][0] + dp0[2][1]) % MOD
        ndp0[2][2] = (dp0[0][0] + dp0[0][1]) % MOD
        ndp1[0] = (dp0[0][0] + dp0[1][2] + dp0[2][1] + sdp1) % MOD
        ndp1[1] = (dp0[1][0] + dp0[2][2] + dp0[0][1] + sdp1) % MOD
        ndp1[2] = (dp0[2][0] + dp0[0][2] + dp0[1][1] + sdp1) % MOD
        dp = ndp
    return (dp[1][sum(map(ord, s)) % 3] + all(a != b for a, b in zip(s, s[1:]))) % MOD


s = input()
print(solve(s))

Solution (Python):
def solve(s):
    if all(a == b for a, b in zip(s, s[1:])):
        return 1
    if len(s) == 2:
        return 2
    elif len(s) == 3:
        if s[0] == s[1] or s[1] == s[2]:
            return 6
        elif s[0] == s[2]:
            return 7
        else:
            return 3
    
    dp = [[[0] * 3 for _ in range(3)] for _ in range(2)]
    dp[0][0][0] = 1
    dp[0][1][1] = 1
    dp[0][2][2] = 1
    MOD = 998244353
    for _ in range(len(s) - 1):
        ndp = [[[0] * 3 for _ in range(3)] for _ in range(2)]
        dp0, dp1 = dp
        ndp0, ndp1 = ndp
        sdp10, sdp11, sdp12 = sum(dp1[0]), sum(dp1[1]), sum(dp1[2])
        ndp0[0][0] = (dp0[0][1] + dp0[0][2]) % MOD
        ndp0[1][0] = (dp0[1][1] + dp0[1][2]) % MOD
        ndp0[2][0] = (dp0[2][1] + dp0[2][2]) % MOD
        ndp0[0][1] = (dp0[2][0] + dp0[2][2]) % MOD
        ndp0[1][1] = (dp0[0][0] + dp0[0][2]) % MOD
        ndp0[2][1] = (dp0[1][0] + dp0[1][2]) % MOD
        ndp0[0][2] = (dp0[1][0] + dp0[1][1]) % MOD
        ndp0[1][2] = (dp0[2][0] + dp0[2][1]) % MOD
        ndp0[2][2] = (dp0[0][0] + dp0[0][1]) % MOD
        ndp1[0][0] = (dp0[0][0] + sdp10) % MOD
        ndp1[1][0] = (dp0[1][0] + sdp11) % MOD
        ndp1[2][0] = (dp0[2][0] + sdp12) % MOD
        ndp1[0][1] = (dp0[2][1] + sdp12) % MOD
        ndp1[1][1] = (dp0[0][1] + sdp10) % MOD
        ndp1[2][1] = (dp0[1][1] + sdp11) % MOD
        ndp1[0][2] = (dp0[1][2] + sdp11) % MOD
        ndp1[1][2] = (dp0[2][2] + sdp12) % MOD
        ndp1[2][2] = (dp0[0][2] + sdp10) % MOD
        dp = ndp
    return (sum(dp[1][sum(map(ord, s)) % 3]) + all(a != b for a, b in zip(s, s[1:]))) % MOD


s = input()
print(solve(s))

Solution (Python):
def solve(s):
    if len(s) == 2:
        return 1 if s[0] == s[1] else 2
    elif len(s) == 3:
        if s[0] == s[1] == s[2]:
            return 1
        elif s[0] == s[1] or s[1] == s[2]:
            return 6
        elif s[0] == s[2]:
            return 7
        else:
            return 3
    if all(a == b for a, b in zip(s, s[1:])):
        return 1
    dp = [[[0] * 3 for _ in range(3)] for _ in range(2)]
    dp[0][0][0] = 1
    dp[0][1][1] = 1
    dp[0][2][2] = 1
    MOD = 998244353
    for _ in range(len(s) - 1):
        ndp = [[[0] * 3 for _ in range(3)] for _ in range(2)]
        ndp[0][0][0] = (dp[0][1][0] + dp[0][2][0]) % MOD
        ndp[0][0][1] = (dp[0][1][1] + dp[0][2][1]) % MOD
        ndp[0][0][2] = (dp[0][1][2] + dp[0][2][2]) % MOD
        ndp[0][1][0] = (dp[0][0][2] + dp[0][2][2]) % MOD
        ndp[0][1][1] = (dp[0][0][0] + dp[0][2][0]) % MOD
        ndp[0][1][2] = (dp[0][0][1] + dp[0][2][1]) % MOD
        ndp[0][2][0] = (dp[0][0][1] + dp[0][1][1]) % MOD
        ndp[0][2][1] = (dp[0][0][2] + dp[0][1][2]) % MOD
        ndp[0][2][2] = (dp[0][0][0] + dp[0][1][0]) % MOD
        ndp[1][0][0] = (dp[0][0][0] + dp[1][0][0] + dp[1][1][0] + dp[1][2][0]) % MOD
        ndp[1][0][1] = (dp[0][0][1] + dp[1][0][1] + dp[1][1][1] + dp[1][2][1]) % MOD
        ndp[1][0][2] = (dp[0][0][2] + dp[1][0][2] + dp[1][1][2] + dp[1][2][2]) % MOD
        ndp[1][1][0] = (dp[0][1][2] + dp[1][0][2] + dp[1][1][2] + dp[1][2][2]) % MOD
        ndp[1][1][1] = (dp[0][1][0] + dp[1][0][0] + dp[1][1][0] + dp[1][2][0]) % MOD
        ndp[1][1][2] = (dp[0][1][1] + dp[1][0][1] + dp[1][1][1] + dp[1][2][1]) % MOD
        ndp[1][2][0] = (dp[0][2][1] + dp[1][0][1] + dp[1][1][1] + dp[1][2][1]) % MOD
        ndp[1][2][1] = (dp[0][2][2] + dp[1][0][2] + dp[1][1][2] + dp[1][2][2]) % MOD
        ndp[1][2][2] = (dp[0][2][0] + dp[1][0][0] + dp[1][1][0] + dp[1][2][0]) % MOD
        dp = ndp
    return (sum(dp[1][x][sum(map(ord, s)) % 3] for x in range(3)) + all(a != b for a, b in zip(s, s[1:]))) % MOD


s = input()
print(solve(s))

Solution (Python):
def main():
    a = raw_input().strip()
    l = len(a)
    if l < 6:
        s = set()
        s.add(a)
        q = [a]
        oa = ord('a')
        while q:
            a = q.pop()
            for i in xrange(l - 1):
                if a[i] != a[i+1]:
                    t = chr(oa + 3 - (ord(a[i]) - oa) - (ord(a[i+1]) - oa))
                    na = a[:i] + t * 2 + a[i+2:]
                    if na not in s:
                        s.add(na)
                        q.append(na)
        print len(s)
        return
    t = a[0] * l
    if t == a:
        print 1
        return
    x = 0
    for c in a:
        if c == 'b':
            x += 1
        elif c == 'c':
            x += 2
    ans = 0
    if all(a[i] != a[i+1] for i in xrange(l - 1)):
        ans += 1
    mod = 998244353
    dp = (1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0)
    for i in xrange(l - 1):
        s = (dp[-1] + dp[-2] + dp[-3]) % mod
        dp = ((dp[3]+dp[6])%mod,(dp[4]+dp[7])%mod,(dp[5]+dp[8])%mod,(dp[2]+dp[8])%mod,(dp[0]+dp[6])%mod,(dp[1]+dp[7])%mod,(dp[1]+dp[4])%mod,(dp[2]+dp[5])%mod,(dp[0]+dp[3])%mod,(dp[0]+dp[5]+dp[7]+s)%mod,(dp[1]+dp[3]+dp[8]+s)%mod,(dp[2]+dp[4]+dp[6]+s)%mod)
    print (ans + dp[9+x%3]) % mod
main()