M - 家 Editorial

Time Limit: 8 sec / Memory Limit: 256 MB

Problem Statement

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

Constraints

  • 2≤H≤1,000,000,0002 ≤ H ≤ 1,000,000,000
  • 1≤R≤161 ≤ R ≤ 16
  • 0≤gi,j≤10 ≤ g_{i,j} ≤ 1
  • gi,i=0g_{i,i} = 0
  • gi,j=gj,ig_{i,j} = g_{j,i}

Input Format

入力は以下の形式で標準入力から与えられる。
HH RR
g1,1g_{1,1} ...... g1,Rg_{1,R}
......
gR.1g_{R.1} ...... gR,Rg_{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

2025-04-03 (Thu)
10:42:08 +00:00