分数: 2 点
问题陈述
给你三个字符串 S_1, S_2, S_3,每个由小写英文字母组成。
查找字符串的数量
重复以下操作即可将 T 长度 N (也由小写英文字母组成)这样没有 S_1, S_2, S_3 作为子序列出现 T。输出答案取模 998244353.
约束
- 1 \leq N \leq 10^3
- S_1, S_2, S_3 是长度最大的非空小写英文字符串 10
- N 是一个整数
输入
输入由标准输入给出,格式如下:
N S_1 S_2 S_3
输出
打印字符串的数量 T 长度 N 由小写英文字母组成,因此没有 S_1, S_2, S_3 作为子序列出现 T,模数 998244353.
示例输入 1
2 abc de f
示例输出 1
624
有 676 长度的字符串 2 由小写英文字母组成。其中, 1 字符串包含 S_2 = de,和 51 字符串包含 S_3 = f。这些集合不重叠。因此,答案是 676 - 1 - 51 = 624.
示例输入 2
4 ab ab ab
示例输出 2
453125
请注意 子序列 的条件不同于 子字符串
长度为 $$$l$$$ 的字符串 $$$s_1s_2 \ldots s_l$$$ 的.
例如, accb 包含 ab 作为子序列,因此不满足条件。
示例输入 3
1000 atcoder algorithm lectures
示例输出 3
669410767