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
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define fi first
#define se second
#define pn printf("\n")
#define ssize(x) int(x.size())
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define bitcount(x) __builtin_popcount(x)
#define clz(x) __builtin_clz(x)
#define ctz(x) __builtin_ctz(x)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef double db;
typedef long double ldb;
#define vv vector
/*void read(int &a){
		char c = getchar_unlocked(); a = 0;
		while(c<'0' || '9'<c) c = getchar_unlocked();
		while('0'<=c&&c<='9') a = (a<<3)+(a<<1)+c-'0', c = getchar_unlocked();
}*/
int inf = 2e09; ll infll = 2e18; int mod = 1e09+7;
int add(int a, int b){return a+b >= mod ? a+b - mod : a+b;}
int sub(int a, int b){return a-b < 0 ? a-b + mod : a-b;}
int mul(int a, int b){return int(a * ll(b) % mod);}
int fpow(int a, int b){
		int ret = 1;
		while(b){
				if(b & 1) ret = mul(ret, a);
				b >>= 1, a = mul(a, a);
		} return ret;
}
int inv(int a){ return fpow(a, mod-2); }
int coeff(int n, int k, vector<int> &fac, vector<int> &invfac){
		if(n < k) return 0;
		return mul(fac[n], mul(invfac[n-k], invfac[k]));
}
void calcfac(int n, vector<int> &fac, vector<int> &invfac){
		fac[0] = 1, invfac[0] = 1;
		for(int i = 1; i <= n; ++i) fac[i] = mul(fac[i-1], i);
		invfac[n] = inv(fac[n]);
		for(int i = n-1; i; --i) invfac[i] = mul(invfac[i+1], i+1);
}
vv<int> newp(vv<int> &a, vv<int> &b){
		vv<int> c(ssize(a));
		for(int i = 0; i < ssize(a); ++i) c[i] = a[b[i]];
		return c;
}
void answer(){
		int n, k; scanf("%d%d", &n, &k);
		vv<vv<int>> g(k, vv<int>(n));
		for(int i = 0; i < k; ++i)
				for(int j = 0; j < n; ++j) scanf("%d", &g[i][j]), --g[i][j];
		map<vv<int>, int> mp;
		queue<vv<int>> q;
		for(int i = 0; i < k; ++i){
				if(!mp[g[i]]) q.emplace(g[i]);
				mp[g[i]] = 1;
		}
		vv<int> tmp;
		int resp = 0, resq = 0;
		while(!q.empty()){
				vv<int> v = q.front(); q.pop();
				for(int i = 0; i < k; ++i){
						tmp = newp(v, g[i]);
						if(!mp[tmp]) mp[tmp] = 1, q.emplace(tmp);
				}
				++resq;
				for(int i = 0; i < n-1; ++i)
						for(int j = i+1; j < n; ++j) if(v[i] > v[j]) ++resp;
				resp %= mod, resq %= mod;
		}
		resp = mul(resp, inv(resq));
		printf("%d\n", resp);
}
signed main(){
		int T = 1;
		//~ scanf("%d", &T);
		//~ ios_base::sync_with_stdio(0); cin.tie(0); //cin >> T;
		for(++T; --T; ) answer();
		return 0;
}