PQ 树是一种表示排列族的树状数据结构。该结构常用于解决各种计算问题，例如图的平面性测试或区间图识别。

$n$ 个元素的 PQ 树是一棵有根树，其顶点分为三种类型：P-顶点、Q-顶点或叶子。任何 P-顶点至少有两个子节点（其子节点初始时是无序的），任何 Q-顶点至少有三个子节点（其子节点初始时是有序的），任何叶子没有子节点。树中恰好有 $n$ 个叶子，它们与 $\{1, \dots, n\}$ 中的不同整数一一对应。

如果可以通过以下方式排列所有内部（P 和 Q）顶点的子节点，则称给定的 PQ 树表示数字 $\{1, \dots, n\}$ 的一个排列 $\sigma$：

• P-顶点的子节点可以任意排列；
• Q-顶点的子节点顺序可以保持不变或反转；
• 当从根节点开始按照所选的子节点顺序遍历树时，叶子被访问的顺序即为排列 $\sigma$。

例如，考虑以下 PQ 树：

显然，该树表示排列 $(1, 2, 3, 4)$ 和 $(4, 3, 2, 1)$，但不表示排列 $(2, 1, 4, 3)$（因为在任何排列中，数字 2 和 3 必须相邻）以及 $(1, 4, 3, 2)$（因为 4 必须位于开头或结尾）。

如果由第一棵树表示的每一个排列也由第二棵树表示，反之亦然，则我们认为这两棵 PQ 树相同；否则，这两棵树是不同的（注意，这意味着反转 Q-顶点的子节点顺序不会改变 PQ 树）。

给定 $k$ 个数字 $\{1, \dots, n\}$ 的排列。计算表示所有给定排列的 $n$ 个叶子的不同 PQ 树的数量。输出答案对 $10^9 + 7$ 取模的结果。

输入格式

第一行包含两个整数 $k$ 和 $n$ ($1 \le k, n \le 500$)。 接下来的 $k$ 行，每行包含 $n$ 个空格分隔的整数：给定的排列。在每一行中，数字两两不同且属于集合 $\{1, \dots, n\}$。

输出格式

输出答案对 $10^9 + 7$ 取模的结果。

样例

样例输入 1

1 2
1 2

样例输出 1

1

样例输入 2

2 4
1 2 3 4
1 2 4 3

样例输出 2

7

样例输入 3

1 5
1 2 3 4 5

样例输出 3

82

说明

两个元素构成的唯一树是带有两个叶子子节点的 P-根树（注意 Q-顶点必须至少有三个子节点）。

满足第二个样例的七棵树如下图所示：