题目描述

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

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

输入格式

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

$N \\$ $t$

输出格式

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

输入输出样例 #1

输入 #1

2
key

输出 #1

6

输入输出样例 #2

输入 #2

2
ccc

输出 #2

0

输入输出样例 #3

输入 #3

100
keyneeneeeckyycccckkke

输出 #3

275429980

说明/提示

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