巫雁要修一条海底电缆通到爱尔齐亚，据某位抱着自己亲爱的 imouto 像咸鱼一样窝在自己房间里睡觉的人类种全权代理人说，提出这个要求是为了方便通信。

这种理由谁信啊

吐槽归吐槽，电缆还是得修，工作还是得做。

电缆内包含 $n$ 种电线，为了方便铺设，这 $n$ 种电线均被分成 $m$ 段进行生产。但为了赶工，所有电线生产时没有控制，导致产量都比 $m$ 要多的多，而且所有电线被错误地混在一起。

电缆的前端（起点）会和巫雁的陆上电缆连接，这一端的陆上电缆内的电线按一定顺序排列——即，电缆内的电线种类形成一个排列，对于第 $i$ 条电线，其种类为 $a_i$，一个 $n$ 长度的排列中的数两两之间互不相等且对于每个下标 $i(1 \le i \le n)$，有 $1 \le a_i \le n$；而电缆的末端（终点）怎么接陆上电缆会由爱尔齐亚这边亲爱的宰相（卑微打工人）想办法，所以电缆末端的电线种类没有要求。最终电缆是由 $m$ 段包含 $n$ 条电线的电缆和起点的开头电缆组成的。

还有一件事：受精灵回廊带来的不可控力影响，每段电缆内的 $n$ 条电线如果存在两条电线种类相同，可能导致电线损坏。正式的：每段电缆内的电线种类也形成一个排列。

已知每种电线与某些其它电线拼接也能正常使用。假设随机选择电线进行铺设，最后电缆能正常投入使用的概率有多大。答案对 $100000007$ 取模。

一行输入两个整数 $n, m$，意义如题意描述。$(1 \le n \le 5, 1 \le m \le 10000)$

第二行输入 $n$ 个整数为从 $a_1$ 到 $a_n$，表示电缆前端连接的陆上电缆的电线种类。

接下来 $n$ 行每行 $n$ 个整数，值均为 $0$ 或 $1$，若第 $i$ 行第 $j$ 列的数为 $1$，则第 $i$ 种电线后接第 $j$ 种电线也可正常使用。（保证当 $i = j$ 时数值为 $1$）

一行输出一个整数，表示电缆能正常使用的概率。

关于题意，可以解释成这样：给定一个 $n$ 行 $m + 1$ 列的矩阵，第 $0$ 列给定，要求每一列必须为一个排列，同时给定一个邻接矩阵表示在题意矩阵中当 $a_{p, q}$ 为数字 $i$ 时 $a_{p, q + 1}$ 为哪些数时合法，求合法方案数和随机安排排列方案数的比值。

对于第二个样例，合法的电线铺设方案只有一种：$[1, 2], [1, 2]$。因此答案为 $\frac{1}{4} \bmod 100000007$。