시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 2 2 2 100.000%

문제

You have a string s consisting of lowercase English letters “a” and “b”.

You can make zero or more operations in any order. Here are the possible operations:

  • Delete “aa” from any place of the string.
  • Delete “bbb” from any place of the string.
  • Delete “ababab” from any place of the string.
  • Add “aa” to any place of the string.
  • Add “bbb” to any place of the string.
  • Add “ababab” to any place of the string.

Your goal is to calculate the number of strings of length x that can be obtained by such operations. As the answer can be very large, find it modulo 998 244 353.

입력

The first line of the input contains one integer n: the length of the string (1 ≤ n ≤ 300 000).

The second line contains a string s of length n consisting of lowercase English letters “a” and “b”.

The third line contains one integer x (0 ≤ x ≤ 109), the length of the string you need to obtain.

출력

Print one integer: the number of strings of length x that can be obtained from string s by making the operations described above, taken modulo 998 244 353.

예제 입력 1

6
ababab
3

예제 출력 1

1

예제 입력 2

3
bbb
2

예제 출력 2

1

예제 입력 3

5
babab
35

예제 출력 3

866826000

출처

Camp > Petrozavodsk Programming Camp > Winter 2019 > Day 1 K번

  • 문제를 만든 사람: 300iq