/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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
出力
答えを出力せよ。
入力例 1
2 2 ab ac
出力例 1
7
入力可能な文字列は aa, ab, ac, ba, bb, ca, cc の 7 つです。
入力例 2
4 3 abcdefg hijklmnop qrstuv wxyz
出力例 2
1352
入力例 3
5 1000000000 abc acde cefg abcfh dghi
出力例 3
346462871
答えを 998244353 で割った余りを出力してください。
Score : 500 points
Problem Statement
We have a typewriter with N rows. The keys in the i-th row from the top can type the characters in a string S_i.
Let us use this keyboard to enter a string, as follows.
- First, choose an integer 1 \le k \le N.
- Then, start with an empty string and only use the keys in the k-th row from the top to enter a string of length exactly L.
How many strings of length L can be entered in this way? Since the answer can be enormous, print it modulo 998244353.
Constraints
- N and L are integers.
- 1 \le N \le 18
- 1 \le L \le 10^9
- S_i is a (not necessarily contiguous) non-empty subsequence of
abcdefghijklmnopqrstuvwxyz.
Input
Input is given from Standard Input in the following format:
N L S_1 S_2 \dots S_N
Output
Print the answer.
Sample Input 1
2 2 ab ac
Sample Output 1
7
We can enter seven strings: aa, ab, ac, ba, bb, ca, cc.
Sample Input 2
4 3 abcdefg hijklmnop qrstuv wxyz
Sample Output 2
1352
Sample Input 3
5 1000000000 abc acde cefg abcfh dghi
Sample Output 3
346462871
Be sure to print the answer modulo 998244353.