Problem Statement

Let s be the concatenation of N copies of keyence.
Consider deleting zero or more characters from s and concatenating the remaining characters without changing the order to make $a new string s^{\prime}$.
There are 2^{7N} ways to choose the positions at which we delete the characters. Among them, how many make $s^{\prime}$ equal to t? Find the count modulo 998244353.

Input

Input is given from Standard Input in the following format:
N
t

Output

Print the number of ways to choose the positions at which we delete the characters so that $s^{\prime}$ will be equal to t, modulo 998244353.

Constraints

• $1 \leq N \leq 10^{18}$
• $1 \leq |t| \leq 2.5 \times 10^5$
• t is a string consisting of c, e, k, n, and y.

Sample Input 1

2
key

Sample Output 1

6

• We have s= keyencekeyence.
• There are six ways to choose the positions at which we delete the characters so that $s^{\prime}=$ key.

Sample Input 2

2
ccc

Sample Output 2

0

• There are zero ways to choose the positions at which we delete the characters so that $s^{\prime}=$ ccc.

Sample Input 3

100
keyneeneeeckyycccckkke

Sample Output 3

275429980

• Be sure to find the count modulo 998244353.

见题面 Input 部分

见题面 Output 部分