分数: 1000 点
问题陈述
让 s 是以下的串联 N 副本 keyence。
考虑删除零个或多个字符 s 并连接剩余的字符而不改变顺序以形成新字符串 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.
示例输入 2
2 ccc
示例输出 2
0
- 有零种方法可以选择删除字符的位置,以便
有一棵树 s^{\prime}=
ccc.
示例输入 3
100 keyneeneeeckyycccckkke
示例输出 3
275429980
- 一定要找到计数模数 998244353.