Contest Duration: ~ (local time) (100 minutes) Back to Home
F - Normalization /

Time Limit: 2 sec / Memory Limit: 256 MB

### 問題文

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

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

### 制約

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

S

abc

### 出力例 1

3

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

abbac

65

babacabac

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.

abc

### Sample Output 1

3

abc, aaa and ccc can be obtained.

abbac

65

babacabac

6310

### Sample Input 4

ababacbcacbacacbcbbcbbacbaccacbacbacba

148010497