题目描述

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

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

输入格式

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

$N$ $t$

输出格式

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

题目大意

题目描述

$s$ 是 keyence 重复 $N$ 次形成的字符串。你可以删除任意个字符（可以是0个）形成新的字符串 $s^{\prime}$。

可以证明有 $2^{7N}$ 个删除方法，你需要找到其中能使 $s^{\prime} = t$ 的方法数，答案对 $998244353$ 取模。

输入格式

第一行，一个整数 $N$，
第二行，一个字符串 $t$。

$N \\$ $t$

输出格式

一行，一个整数，表示满足题意的方法数对 $998244353$ 取模的值。

提示

数据范围

• $1\ \leq\ N\ \leq\ 10^{18}$
• $1\ \leq\ |t|\ \leq\ 2.5\ \times\ 10^5$，$|t|$ 代表字符串 $t$ 的长度
• $t$ 是只包含 c, e, k, n, y 的字符串

2
key

6

2
ccc

0

100
keyneeneeeckyycccckkke

275429980

提示

制約

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

Sample Explanation 1

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

Sample Explanation 2

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

Sample Explanation 3

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