|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|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:
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
3 bbb 2
5 babab 35