题目描述

$N$ 段からなるタイプライターがあります。このうち、上から $i$ 段目のキーでは文字列 $S_i$ に含まれる文字が打てます。

このキーボードを使って、以下のルールで文字列をひとつ入力することを考えます。

• まず、整数 $1\ \le\ k\ \le\ N$ を選択する。
• その後、空文字列から始めて、上から $k$ 段目にあるキーだけを使ってちょうど $L$ 文字の文字列を入力する。

このルールに従って入力可能な $L$ 文字の文字列は何通りありますか？ 答えは非常に大きくなる場合があるので $998244353$ で割った余りを出力してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $L$ $S_1$ $S_2$ $\dots$ $S_N$

输出格式

答えを出力せよ。

题目大意

给定 $n$ 个字符串，字符集为小写字母，可以任意选择一个字符串，作为字符库，然后（可多次选择同一字符）任意组成长度为 $l$ 的字符串，求一共能形成多少种长度为 $l$ 的字符串。

请输出方案数模 $998244353$。

2 2
ab
ac

7

4 3
abcdefg
hijklmnop
qrstuv
wxyz

1352

5 1000000000
abc
acde
cefg
abcfh
dghi

346462871

提示

制約

• $N,L$ は整数
• $1\ \le\ N\ \le\ 18$
• $1\ \le\ L\ \le\ 10^9$
• $S_i$ は abcdefghijklmnopqrstuvwxyz の(連続とは限らない)空でない部分列

Sample Explanation 1

入力可能な文字列は aa, ab, ac, ba, bb, ca, cc の $7$ つです。

Sample Explanation 3

答えを $998244353$ で割った余りを出力してください。