시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 10 | 10 | 8 | 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:
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.
6 ababab 3
1
3 bbb 2
1
5 babab 35
866826000
Camp > Petrozavodsk Programming Camp > Winter 2019 > Day 1: 300iq Contest K번