F - Keyence Repetition /

### 問題文

skeyenceN 回繰り返した文字列とします。 s0 個以上の文字を削除した後、残った文字を元の順序を保ったまま連結して新しい文字列 s^{\prime} を作ることを考えます。

### 制約

• 1 \leq N \leq 10^{18}
• 1 \leq |t| \leq 2.5 \times 10^5
• tc, e, k, n, y のみからなる文字列

### 入力

N
t


### 入力例 1

2
key


### 出力例 1

6

• s= keyencekeyence です。
• s^{\prime}= key となるような削除する位置の選び方は 6 通りです。

### 入力例 2

2
ccc


### 出力例 2

0

• s^{\prime}= ccc となるような削除する位置の選び方は 0 通りです。

### 入力例 3

100
keyneeneeeckyycccckkke


### 出力例 3

275429980

• 998244353 で割ったあまりを求めるのを忘れずに。

Score : 1000 points

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

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

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

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