#1006. F. “全天候”壮大,CSF效应

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: JM233333

题目描述

随着“全天候”量化团队在校内外闯出名气,你也成了校内名人,甚至你周围xjtu的同学们发现,你的名字csf总是伴随着强大的力量。例如在考试前,如果他们复习时在书上看到了csfnb的字样,那么这次考试就稳了;更惊为天人的是,即使csfnb不连续(例如如下字符串ccssdddnb含有子序列csfnb),满分奇迹同样会发生。当然,学生们的阅读能力有限,如果如果这个子序列的首尾字符距离太远(大于k),那么他们就看不出来csfnb了。现在问题来了:给定一个字符串,里面有多少个子序列是csfnb,且满足子序列的首尾字符距离小于等于kk呢?

你认为不能只有你nb啊,于是把题改成了这样:

给定一个长字符串SS,在给定一个短字符串TT,问里面有多少个子序列是TT,且满足子序列的首尾字符距离小于等于kk呢?

由于答案可能很大,请输出答案对998244353998244353取模。

输入格式

第一行一个正整数kk,第二行一个字符串SS,第三行一个字符串TT

输出格式

输出一行一个整数表示答案。

样例

样例输入 样例输出
9
ccssffdddnb
csfnb
4

数据范围与提示

1S1051 \leq |S| \le 10^5

1T201 \leq |T| \le 20

0k<S0 \le k < |S|