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
#include<bits/stdc++.h>

using namespace std;

const short N = 3000 + 5;
const int Mod = 1e9 + 7;

inline int power(int x, int y){
	int ret = 1;
	while(y){
		if(y & 1) ret = 1ll * ret * x % Mod;
		x = 1ll * x * x % Mod, y >>= 1;
	}
	return ret;
}

inline int inv(int x){
	return power(x, Mod - 2);
}

int a = 0, b = 0, c = 0, ans = 0;
short n = 0, k = 0, p[N][N] = {};
bool ok = 0, vis[N][N] = {}, tag[N][N] = {};
vector<pair<short, short> > vec;

inline void dfs(short x, short y){
	vis[x][y] = 0, tag[y][x] = 1, c ++;
	if(x != y){
		if(x < y) a ++; if(y < x) b ++;
		vec.push_back(make_pair(y, x));
	}
	short *u = p[x], *v = p[y];
	for(short i = 1 ; i <= k ; i ++) if(vis[u[i]][v[i]]){
		if(tag[u[i]][v[i]]) ok = 1;
		else dfs(u[i], v[i]);
	}
}

int main(){
	ios :: sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> k;
	for(short i = 1 ; i <= k ; i ++) for(short x = 1 ; x <= n ; x ++) cin >> p[x][i];
	for(short x = 1 ; x <= n ; x ++) for(short y = 1 ; y <= n ; y ++) vis[x][y] = 1;
	for(short x = 1 ; x <= n ; x ++) for(short y = 1 ; y <= n ; y ++) if(vis[x][y]){
		a = 0, b = 0, c = 0, ok = 0, vec.clear();
		dfs(x, y);
		for(auto bag : vec){
			short x = bag.first, y = bag.second;
			vis[x][y] = 0;
			if(ok){
				c ++;
				if(x < y) a ++; if(x > y) b ++;
			}
		}
		if(ok) ans = (ans + 1ll * a * b % Mod * inv(c)) % Mod;
		else ans = (ans + 2ll * a * b % Mod * inv(c)) % Mod;
	}
	cout << ans << '\n';
	return 0;
}