Typical DP Contest

Q - 連結


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 262.144MB

Problem Statement

N 個の 0, 1 からなる文字列 w_1, ..., w_N がある。すぬけ君は、この中から文字列をいくつか選び、好きな順番で連結して文字列を作ることにした (同じ文字列を複数回選んでもよい)。このようにして作ることのできる長さ L の文字列の個数を mod 1,000,000,007 で求めよ。ただし、文字列として同じであれば、連結のしかたが異なるものも同じであるとみなす。

Constraints

  • 1 ≤ N ≤ 510
  • 1 ≤ |w_i| ≤ 8
  • 1 ≤ L ≤ 100
  • Each character in w_i will be either '0' or '1'.
  • w_i are pairwise distinct.

Input Format

入力は以下の形式で標準入力から与えられる。
N L
w_1
...
w_N

Output Format

答えを一行に出力せよ。

Sample Input 1

4 10
00
01
10
11

Sample Output 1

1024
0, 1 からなる長さ 10 の文字列がすべて作れることがわかる。

Sample Input 2

3 5
01
10
0

Sample Output 2

14

Submit提出する