AT_tdpc_house 家

你的房间有 $H$ 层，每个楼层都有相同的构造。每层有 $R$ 个房间，当且仅当 $g_{i,j}=1$ 时房间 $i$ 和房间 $j$ 之间有双向通路。另外，能够利用楼梯从 $h$ 层的房间 $r$ 下来到 $h-1$ 层的房间 $r$（不能上楼）。 求出从 $H$ 层的房间 $1$ 到 $1$ 层的房间 $1$ 不能走相同房间的路径的个数，对 $10^9+7$ 取模。

> $H$ $R$\ $g_{1,1} ... g_{1,R}$\ ...\ $g_{R,1} ... g_{R,R}$

答案输出为一行。

$2\le H\le10^9,1\le R\le 16,g_{i,j}\in\{0,1\}$。保证 $g_{i,i}=0,g_{i,j}=g_{j,i}$。