巫雁要修一条海底电缆通到爱尔齐亚，据某位抱着自己亲爱的 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。