← 返回题目列表

AtCoder · tdpc_house

M. 家

中文机器翻译题面 查看原题

问题陈述

Snuke 的房子是 H 这是一栋三层楼房,每层的结构都相同。每层楼 有 R 个房间和 i 和房间 j 当 g_{i,j} = 1 时,存在双向路径。另外,h 楼层房间 您可以使用楼梯下去到 r 减去 h-1 楼层房间 您可以使用楼梯下去到 r 。(PS:h、r为任意整数) (无法攀爬。) H 从楼层 1 号房间 1 使用 mod 1,000,000,007 求出在不经过同一个房间的情况下到达该层房间 1 的路线数。

约束

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

输入格式

输入是按以下格式从标准输入给出的。
H R
g_{1,1} ... g_{1,R}
...
g_{R.1} ... g_{R,R}

输出格式

请将答案输出为一行。

示例输入 1

10 2
0 1
1 0

示例输出 1

512

示例输入 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

示例输出 2

1025