← 返回题目列表

AtCoder · abc419_f

I. 全部包含

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

分数: 550 点

问题陈述

你被给予 N 小写英文字符串 S_1,S_2,\ldots,S_N,和一个整数 L.

求模数 998244353,长度-L 小写英文字符串,包含所有 S_1,S_2,\ldots,S_N 作为子字符串。

什么是子串? A 子字符串 of S 是从开头删除零个或多个字符,从结尾删除零个或多个字符得到的字符串 S.
例如, ab, bc,和 bcd 是子串 abcd,同时 ac, dc,和 e 不是以下的子串 abcd.

约束

  • 1\leq N\leq 8
  • 1\leq L\leq 100
  • N 和 L 是整数。
  • 每个 S_i 是一个长度为的字符串 1 和 10,包含在内,由小写英文字母组成。
  • S_i\neq S_j\ (i\neq j)

输入

输入由标准输入按以下格式给出:

N L
S_1
S_2
\vdots
S_N

输出

输出答案。


示例输入 1

2 4
ab
c

示例输出 1

153

满足条件的一些字符串是 abcz 和 cabc. acbd 不包含 ab 作为子字符串,因此不满足条件。


示例输入 2

2 6
abc
cde

示例输出 2

54

示例输入 3

5 50
bbfogggj
zkbach
eedirhyc
ffgd
oemmswj

示例输出 3

689020583