配点 : $500$ 点

問題文

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

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

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

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

制約

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

入力

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

$N$ $L$

$S_1$

$S_2$

$\dots$

$S_N$

出力

答えを出力せよ。

2 2
ab
ac

7

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

4 3
abcdefg
hijklmnop
qrstuv
wxyz

1352

5 1000000000
abc
acde
cefg
abcfh
dghi

346462871

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