F - Normalization Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 700 点

問題文

a,b,c からなる文字列 S が与えられます。次の操作を 0 回以上繰り返して作ることのできる文字列としてありうるものの個数を 998244353 で割ったあまりを求めてください。

  • 1\leq i\leq |S|-1 かつ S の i 文字目と i+1 文字目が異なるような整数 i を選ぶ。S の i 文字目と i+1 文字目を両方、(a,b,c のうち)そのどちらとも異なる文字で置き換える。

制約

  • 2 \leq |S| \leq 2 × 10^5
  • S は a,b,c からなる

入力

入力は以下の形式で標準入力から与えられる。

S

出力

操作を繰り返して作ることのできる文字列としてありうるものの個数を 998244353 で割ったあまりを出力せよ。

入力例 1

abc

出力例 1

3

abc,aaa,ccc を作ることができます。

入力例 2

abbac

出力例 2

65

入力例 3

babacabac

出力例 3

6310

入力例 4

ababacbcacbacacbcbbcbbacbaccacbacbacba

出力例 4

148010497

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