1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include<bits/stdc++.h>
using namespace std;

vector<int>aplikuj(vector<int>f, vector<int>g){
	vector<int>wynik(f.size(), 0);
	for(int i=0;i<(int)f.size();i++)
		wynik[i] = g[f[i]];
	return wynik;
}
map<vector<int>, int>legenda;
vector<vector<int>>dostepne;
vector<vector<int>>graf;
bool odw[5000010];
void dfs(int x){
	odw[x] = 1;
	for(auto j: dostepne){
		auto pom = aplikuj(j, graf[x]);
		if(!odw[legenda[pom]])
			dfs(legenda[pom]);
	}
}
int ile[12][12];
const long long mod = 1000000007;
long long qp(long long a, long long b){
	if(b==0)return 1;
	if(b%2)return qp(a, b-1)*a%mod;
	long long c = qp(a, b/2);
	return c*c%mod;
}
int odw1[5000010];
int inv(vector<int>pom){
	int res = 0;
	for(int i=0;i<(int)pom.size();i++)
		for(int j = i+1;j<(int)pom.size();j++)
			if(pom[i]>pom[j])
				res++;
	return res;
}
int main()
{
	int n, i;
	scanf("%d", &n);
	vector<int>pom;
	for(i=0;i<n;i++)
		pom.push_back(i);
	do{
		legenda[pom] = (int)graf.size();
		graf.push_back(pom);
	}while(next_permutation(pom.begin(), pom.end()));
	int k, K;
	scanf("%d", &k);K = k;
	vector<int>inversions;
	while(k--){
		vector<int>perm;
		for(i=0;i<n;i++){
			perm.push_back(0);
			scanf("%d", &perm.back());
			perm.back()--;
		}
		inversions.push_back(inv(perm));
		dostepne.push_back(perm);
	}
	dfs(0);
//	return 0;
	int zlicz = 0;
	int suma = 0;
	for(auto j:legenda){
		if(odw[j.second]){
			zlicz++;
			for(i=0;i<n;i++)
				for(int ij=i+1;ij<n;ij++)
					if(j.first[i]>j.first[ij])
						ile[i][ij]++;
//			for(auto ij: j.first)
//				printf("%d ", ij);printf("\n");
		}
	}
	for(i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
//			printf("%d ", ile[i][j]);
			suma+=ile[i][j];
		}
//		printf("\n");
	}
	printf("%lld\n", qp(zlicz, mod-2)*suma%mod);
	//printf(" = %lld / %lld\n", suma, zlicz);
	return 0;

	sort(inversions.begin(), inversions.end());
	/*
	if((int)inversions.size()==3 && inversions[0]==1 && inversions[1]==2 && inversions[2]==2)
	{
		printf("n:%d inv:", n);
		for(auto j: inversions)printf("%d ", j);printf(":\n");
		printf("%lld\n", qp(zlicz, mod-2)*suma%mod);
	//	printf(" = %lld / %lld\n", suma, zlicz);
	}*/
}