题目描述

有一个 $N\times N$ 的国际象棋棋盘，以及 $K$ 个互不相同的车，编号为 $0,1,\ldots,K-1$。每个格子至多放一个车。

给定一个 $K\times K$ 的 01 矩阵 graph。对于任意 $i,j$：

• 若 graph[i][j] = '1'，则车 $i$ 与车 $j$ 必须位于同一行或同一列；
• 若 graph[i][j] = '0'，则车 $i$ 与车 $j$ 必须既不同行也不同列。

求满足所有限制的摆放方案数，对 $10^9+7$ 取模。

车是有编号的，因此交换两个车的位置通常会产生不同方案。

输入格式

第一行输入两个整数 $K,N$。注意：真实数据中车的数量 $K$ 在前，棋盘大小 $N$ 在后。

接下来输入 $K$ 行，每行一个长度为 $K$ 的 01 字符串，组成矩阵 graph。

输出格式

输出合法摆放方案数对 $10^9+7$ 取模后的结果。

数据范围

• $1\le N\le50$；
• $1\le K\le50$；
• graph[i][i] = '1'；
• graph 为对称矩阵；
• 每个字符均为 0 或 1。

样例

2 8
11
11

896

样例说明

车 $0$ 有 $8^2=64$ 个位置。固定车 $0$ 后，车 $1$ 可以放在同一行其余 $7$ 个格子或同一列其余 $7$ 个格子，共 $14$ 种，因此答案为 $64\times14=896$。