Rhason Cheung 有一个简单的问题，并向 Mai 老师寻求帮助。但 Mai 老师认为这个问题太简单了，有时甚至有些幼稚。所以她让你来帮忙。

Mai 老师有 $m$ 个函数 $f_1, f_2, \dots, f_m : \{1, 2, \dots, n\} \to \{1, 2, \dots, n\}$（这意味着对于所有的 $x \in \{1, 2, \dots, n\}$，都有 $f(x) \in \{1, 2, \dots, n\}$）。但 Rhason 只知道其中一些函数，其他的函数是未知的。

她想知道有多少种不同的函数序列 $f_1, f_2, \dots, f_m$，使得对于每一个 $i$ ($1 \le i \le n$)，都有 $f_1(f_2(\dots f_m(i)\dots)) = i$。两个函数序列 $f_1, f_2, \dots, f_m$ 和 $g_1, g_2, \dots, g_m$ 被认为是不同的，当且仅当存在 $i$ ($1 \le i \le m$) 和 $j$ ($1 \le j \le n$)，使得 $f_i(j) \neq g_i(j)$。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 50$)。

对于每个测试用例，第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 100$)。

接下来有 $m$ 行。在第 $i$ 行中，包含一个数字 $-1$ 或 $n$ 个空格分隔的整数。如果只有一个数字 $-1$，则表示函数 $f_i$ 是未知的。否则，第 $i$ 行中的第 $j$ 个数字表示 $f_i(j)$。

输出格式

对于每个测试用例，输出答案对 $10^9 + 7$ 取模的结果。

样例

输入 1

1
3 3
1 2 3
-1
3 2 1

输出 1

1