D - Shift Assignment Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君が働く職場では、日々の勤務形態として「シフト A」と「シフト B」の 2 種類があります。

現在、高橋君の今後 N 日間の勤務計画を表す長さ N の文字列 S が与えられます。

S の i 番目の文字（1 \le i \le N）は i 日目の勤務予定を表しており、それぞれ以下の意味を持ちます。

  • A ：シフト A に入ることが確定している。
  • B ：シフト B に入ることが確定している。
  • C ：シフトが未定である。

高橋君は、S に含まれるすべての C をそれぞれ独立に A または B に置き換えることで、すべての日についてシフト A またはシフト B のどちらかを割り当てようとしています。

この職場では、健康管理の観点からシフト A に 2 日連続で入ることが禁止されているため、置き換え後の文字列において A が 2 つ連続してはなりません（すなわち、置き換え後の文字列が連続部分文字列として AA を含んではいけません）。

条件を満たす置き換え方の総数を 998244353 で割った余りを求めてください。なお、条件を満たす置き換え方が 1 つも存在しない場合は 0 を出力してください。

制約

  • 1 \le N \le 2 \times 10^6
  • N は整数
  • S は A, B, C のみからなる長さ N の文字列

入力

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

N
S

出力

答えを 998244353 で割った余りを 1 行で出力してください。

入力例 1

4
ACBC

出力例 1

2

入力例 2

5
CBAAC

出力例 2

0

入力例 3

15
CCBACBCBCCABCCC

出力例 3

60

入力例 4

50
CBCCBCACBCBCACBCBCCBCBCBACBCCBCACBCBCACBCBCCBCBCBA

出力例 4

41472

入力例 5

1
C

出力例 5

2

Score : 366 pts

Problem Statement

At Takahashi's workplace, there are two types of daily shifts: Shift A and Shift B.

You are given a string S of length N representing Takahashi's work schedule for the next N days.

The i-th character of S (1 \le i \le N) represents the work schedule for the i-th day, with the following meanings:

  • A: Confirmed to work Shift A.
  • B: Confirmed to work Shift B.
  • C: The shift is undecided.

Takahashi wants to assign either Shift A or Shift B to each day by independently replacing every C in S with either A or B.

At this workplace, working Shift A on two consecutive days is prohibited for health management reasons. Therefore, there must not be two consecutive A's in the string after replacement (that is, the resulting string must not contain AA as a contiguous substring).

Find the number of valid ways to replace the characters, modulo 998244353. If no valid replacement exists, output 0.

Constraints

  • 1 \le N \le 2 \times 10^6
  • N is an integer.
  • S is a string of length N consisting only of A, B, and C.

Input

The input is given from Standard Input in the following format:

N
S

Output

Print the answer modulo 998244353 in a single line.

Sample Input 1

4
ACBC

Sample Output 1

2

Sample Input 2

5
CBAAC

Sample Output 2

0

Sample Input 3

15
CCBACBCBCCABCCC

Sample Output 3

60

Sample Input 4

50
CBCCBCACBCBCACBCBCCBCBCBACBCCBCACBCBCACBCBCCBCBCBA

Sample Output 4

41472

Sample Input 5

1
C

Sample Output 5

2