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 f1,f2,...,fm:{1,2,...,n}→{1,2,...,n}(that means for all x∈{1,2,...,n}，f(x)∈{1,2,...,n}.
But Rhason only knows some of these functions, and others are unknown.
She wants to know how many different function series f1,f2,...,fm there are that for every i(i≤1≤n),f1(f2(...(fm(i))...))=i. Two function series f1,f2,...,fm and g1,g2,...,gm are considered different if and only if there exist i(1≤i≤m), j(1≤j≤n),fi(j)≠gi(j)
Input
For each test case, the first lines contains two numbers n,m(1≤n,m≤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 fi is unknown. Otherwise the j-th number in the i-th line means fi(j)
Output
For each test case print the answer modulo 109+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.
题意：
求满足f1(f2(...(fm(i))...))=i的未知的函数有多少种可能。
分析：
答案是(n!)^(m-1)再mod 109+7,m为-1的个数，因为m个不确定的函数，其中的m-1个固定了，那么还有一个也就固定了。每个不确定的都有n!种方案。
如果m为0，则有0种或者1种方案。也就是要看当前的一层一层能否推到f1(f2(...(fm(i))...))=i。
要注意：当某个f里1..n没有全部出现时，即有重复数字时，答案是0。
这题说是too simple，然而好多坑啊！样例只有一组数据，但是实际上可能有多组数据，除此，要注意每次处理新的一组时，哪些变量要清零，还有这题要用long long，n阶乘可以在一开始初始化。
代码：
#include<stdio.h>
#define M 1000000007LL
#define ll long long
#define N 105
#define F(a,b,c) for(int a=b;a<=c;a++)
ll n,m,d,f[N][N],y[N],jc[N]={,},ans;
int main()
{
F(i,,)jc[i]=jc[i-]*i%M;//初始化阶乘
while(~scanf("%lld%lld",&n,&m))
{
d=;ans=;//初始化
F(i,,m)
{
scanf("%lld",&f[i][]);
if(f[i][]==-)d++;
else F(j,,n)
{
scanf("%lld",&f[i][j]);
if(ans)F(k,,j-)
if(f[i][j]==f[i][k])ans=;
}
}
if(ans)
{
if(d==)
{
F(i,,n)y[i]=i;
for(int i=m; i; i--)
F(j,,n)y[j]=f[i][y[j]];//一层层推到f1
F(i,,n&&ans)if(y[i]!=i)ans=;
}
else
F(i,,d-)ans=ans*jc[n]%M;
}
printf("%lld\n",ans);
}
return ;
}