Q - 連結
解説
/
N 個の 0, 1 からなる文字列 w_1, ..., w_N がある。すぬけ君は、この中から文字列をいくつか選び、好きな順番で連結して文字列を作ることにした (同じ文字列を複数回選んでもよい)。このようにして作ることのできる長さ L の文字列の個数を mod 1,000,000,007 で求めよ。ただし、文字列として同じであれば、連結のしかたが異なるものも同じであるとみなす。
入力は以下の形式で標準入力から与えられる。
答えを一行に出力せよ。
0, 1 からなる長さ 10 の文字列がすべて作れることがわかる。
実行時間制限: 2 sec / メモリ制限: 256 MB
Problem Statement
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
Sample Input 2
3 5 01 10 0
Sample Output 2
14