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


### 入力例 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