K. Knowledge
time limit per test
1 second
memory limit per test
256 mebibytes
input
standard input
output
standard output

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$$$.

Input

The first line of the input contains one integer $$$n$$$: the length of the string ($$$1 \leq n \leq 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 \leq x \leq 10^9$$$), the length of the string you need to obtain.

Output

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$$$.

Examples
Input
6
ababab
3
Output
1
Input
3
bbb
2
Output
1
Input
5
babab
35
Output
866826000