← 返回题目列表

AtCoder · ndpc2026_c

C. 字符串

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

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