← 返回题目列表

AtCoder · keyence2021_f

F. 基恩士重复

中文机器翻译题面 查看原题

分数: 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.