200943: [AtCoder]ARC094 F - Normalization
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
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
andc
).
Constraints
- $2 \leq |S| \leq 2 × 10^5$
- $S$ consists of
a
,b
andc
.
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