#P13790. [keyence2021]Keyence Repetition

    ID: 12991 传统题 6000ms 1024MiB 尝试: 3 已通过: 1 难度: 9 上传者: 标签>CF2700省选/NOI-双射计数普通生成函数转移矩阵乘积分治乘积NTT阶乘逆元预处理

[keyence2021]Keyence Repetition

题目描述

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

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

输入格式

第一行,一个整数 NN,
第二行,一个字符串 tt。

N N \\ t t

输出格式

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

输入输出样例 #1

输入 #1

2
key

输出 #1

6

输入输出样例 #2

输入 #2

2
ccc

输出 #2

0

输入输出样例 #3

输入 #3

100
keyneeneeeckyycccckkke

输出 #3

275429980

说明/提示

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