#P10990. [2015杭电多校]Too Simple

    ID: 10132 传统题 3000ms 256MiB 尝试: 1 已通过: 1 难度: 4 上传者: 标签>CF1500普及+/提高-置换乘法原理排列数计算快速幂直接模拟

[2015杭电多校]Too Simple

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 mm functions $f_1,f_2,\cdots,f_m:\{1,2,\cdots,n\}\to\{1,2,\cdots,n\}$(that means for all x∈{1,2,⋯ ,n},f(x)∈{1,2,⋯ ,n}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 f1,f2,⋯ ,fmf_1,f_2,\cdots,f_m there are that for every i(1≤i≤n)i(1\leq i\leq n),f1(f2(⋯fm(i)))=if_1(f_2(\cdots f_m(i)))=i. Two function series f1,f2,⋯ ,fmf_1,f_2,\cdots,f_m and g1,g2,⋯ ,gmg_1,g_2,\cdots,g_m are considered different if and only if there exist i(1≤i≤m),j(1≤j≤n)i(1\leq i\leq m),j(1\leq j\leq n),fi(j)≠gi(j)f_i(j)\neq g_i(j).

Input

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

Output

For each test case print the answer modulo 109+710^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