M - 家
Editorial
/
すぬけ君の家は 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 で求めよ。
入力は以下の形式で標準入力から与えられる。
答えを一行に出力せよ。
Time Limit: 8 sec / Memory Limit: 256 MB
Problem Statement
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