对于两个长度为 $n$ 的排列 $A$ 和 $B$，Randias 可以通过以下方式生成一个长度为 $n$ 的排列 $C = A \circ B$：对于每个 $1 \le i \le n$，$C[i] = A[B[i]]$。

现在给定 $m$ 个长度均为 $n$ 的排列 $A_1, A_2, \dots, A_m$。他想要选择一个非空的下标集合 $i_1, i_2, \dots, i_k$（其中 $1 \le k \le m, 1 \le i_1 < i_2 < \dots < i_k \le m$），并计算 $C = (((A_{i_1} \circ A_{i_2}) \circ A_{i_3}) \circ A_{i_4}) \dots \circ A_{i_k}$。Randias 想知道他能生成多少种不同的排列 $C$？请输出答案对 $10^9 + 7$ 取模的结果。

长度为 $n$ 的排列是指一个由 $1$ 到 $n$ 的 $n$ 个不同整数以任意顺序组成的数组。例如，$[2, 3, 1, 5, 4]$ 是一个排列，但 $[1, 2, 2]$ 不是排列（$2$ 在数组中出现了两次），$[1, 3, 4]$ 也不是排列（$n=3$ 但数组中出现了 $4$）。

输入格式

第一行包含两个正整数 $n, m$ ($1 \le n \cdot m \le 180$)，分别表示排列的长度和排列的个数。

接下来的 $m$ 行，每行包含 $n$ 个不同的整数，表示一个排列。

输出格式

输出一个整数，表示 Randias 可以生成的不同排列 $C$ 的数量，对 $10^9 + 7$ 取模。

样例

样例输入 1

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

样例输出 1

8

样例输入 2

2 1
2 1

样例输出 2

1