给定一棵未知有根树的 $m$ 个深度优先搜索（DFS）序。

我们考虑包含 $n$ 个顶点（编号从 $1$ 到 $n$）的有根树，其中顶点 $1$ 是根。该树是无向连通的，并且恰好有 $n - 1$ 条边。

DFS 的定义。 对于一棵固定的有根树，其 DFS 序通过以下方式获得：

• 所有顶点初始时均为未访问状态。
• 从根节点 $1$ 开始，将其标记为已访问并输出。
• 当你位于某个顶点 $v$ 时，考虑该有根树中 $v$ 的所有子节点。以 任意 顺序选择它的子节点。对于每个选定的且仍未访问的子节点 $u$，移动到 $u$，将其标记为已访问，输出 $u$，并以相同的方式从 $u$ 继续进行 DFS。

对于一棵固定的树，处理每个顶点子节点的不同顺序可能会产生不同的 DFS 序。所有的 DFS 序都是 $1, 2, \dots, n$ 的排列，并且总是以 $1$ 开头。

给定 $m$ 个 $1, 2, \dots, n$ 的排列，每个排列都以 $1$ 开头。已知它们都是 同一棵 有根树（以 $1$ 为根）在上述定义意义下的 DFS 序（在不同的 DFS 过程中可能使用了不同的子节点顺序）。

你的任务是确定有多少棵不同的有根树可以产生 所有 这 $m$ 个 DFS 序。

如果两棵有根树的边集不同，则认为它们是不同的。

由于答案可能非常大，你应该输出其对 $10^9 + 7$ 取模后的结果。

输入格式

第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 500$）。

接下来的 $m$ 行，每行包含一个整数 $1, 2, \dots, n$ 的排列 $p_{k,1}, p_{k,2}, \dots, p_{k,n}$，描述第 $k$ 个 DFS 序。

对于每个 $k$，所有的 $p_{k,i}$ 互不相同，且 $p_{k,1} = 1$。

输出格式

输出一个整数：顶点集为 $1, 2, \dots, n$ 且以 $1$ 为根的有根树的数量，使得 每一个 给定的序列都是该树的合法 DFS 序，结果对 $10^9 + 7$ 取模。

样例

样例输入 1

3 2
1 2 3
1 3 2

样例输出 1

1

样例输入 2

4 1
1 2 3 4

样例输出 2

5

样例输入 3

5 2
1 2 3 4 5
1 2 4 3 5

样例输出 3

3