M - 家 Editorial /

Time Limit: 8 sec / Memory Limit: 256 MB

Problem Statement

すぬけ君の家は H 階建てであり、どの階も同じ構造をしている。各階には R 個の部屋があり、部屋 i と部屋 j の間には g_{i,j} = 1 であるとき bidirectional な通路がある。また、h 階の部屋 r から h-1 階の部屋 r に階段を使って降りることができる。(追記 : h, r は任意の整数) (登ることはできない。)　H 階の部屋 1 から 1 階の部屋 1 に同じ部屋をとおらずに行く経路の個数を mod 1,000,000,007 で求めよ。

Constraints

  • 2 ≤ H ≤ 1,000,000,000
  • 1 ≤ R ≤ 16
  • 0 ≤ g_{i,j} ≤ 1
  • g_{i,i} = 0
  • g_{i,j} = g_{j,i}

Input Format

入力は以下の形式で標準入力から与えられる。
H R
g_{1,1} ... g_{1,R}
...
g_{R.1} ... g_{R,R}

Output Format

答えを一行に出力せよ。

Sample Input 1

10 2
0 1
1 0

Sample Output 1

512

Sample Input 2

2 5
0 1 1 1 1
1 0 1 1 1
1 1 0 1 1
1 1 1 0 1
1 1 1 1 0

Sample Output 2

1025