Too Simple

Problem Description

Rhason Cheung had a simple problem, and asked Teacher Mai for help. But Teacher Mai thought this problem was too simple, sometimes naive. So she ask you for help. Teacher Mai has $m$ functions $f_1,f_2,\cdots,f_m:\{1,2,\cdots,n\}\to\{1,2,\cdots,n\}$(that means for all $x \in \{1,2,\cdots,n\},f(x)\in \{1,2,\cdots,n\}$). But Rhason only knows some of these functions, and others are unknown. She wants to know how many different function series $f_1,f_2,\cdots,f_m$ there are that for every $i(1\leq i\leq n)$,$f_1(f_2(\cdots f_m(i)))=i$. Two function series $f_1,f_2,\cdots,f_m$ and $g_1,g_2,\cdots,g_m$ are considered different if and only if there exist $i(1\leq i\leq m),j(1\leq j\leq n)$,$f_i(j)\neq g_i(j)$.

Input

For each test case, the first lines contains two numbers $n,m(1\leq n,m\leq 100)$. The following are $m$ lines. In $i$-th line, there is one number $-1$ or $n$ space-separated numbers. If there is only one number $-1$, the function $f_i$ is unknown. Otherwise the $j$-th number in the $i$-th line means $f_i(j)$.

Output

For each test case print the answer modulo $10^9+7$.

Sample Input

3 3
1 2 3
-1
3 2 1

Sample Output

1

Hint

The order in the function series is determined. What she can do is to assign the values to the unknown functions.

Author

xudyh

Source

2015 Multi-University Training Contest 9