F - Keyence Repetition Editorial /

Time Limit: 6 sec / Memory Limit: 1024 MB

配点 : 1000 点

問題文

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

削除する位置の選び方は 2^{7N} 通りあります。これらのうち、s^{\prime} が t と一致するようなものの個数を 998244353 で割ったあまりを求めてください。

制約

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

入力

入力は以下の形式で標準入力から与えられる。

N
t

出力

削除する位置の選び方のうち、s^{\prime} が t と一致するようなものの個数を 998244353 で割ったあまりを出力せよ。

入力例 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.