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
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> BI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(114514); 
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

const int N=3010;
int n,k,p[N*2][N],pp[110][N];
int v[N],vv[N],od[N*2];
bool vis[N][N];
ll ans;

int M=50;

int main() {
	scanf("%d%d",&n,&k);
	//n=3000; k=3000;
	rep(i,0,k) {
		rep(j,0,n) scanf("%d",&p[i][j]),--p[i][j];
		//rep(j,0,n) p[i][j]=j; shuffle(p[i],p[i]+n,mrand);
		rep(j,0,n) p[k+i][p[i][j]]=j;
	}
	rep(i,0,M) {
		rep(j,0,n) v[j]=j;
		rep(j,0,2*k) od[j]=j;
		shuffle(od,od+2*k,mrand);
		rep(j,0,2*k) if (rnd(2)) {
			int o=od[j];
			rep(k,0,n) vv[k]=v[p[o][k]];	
			memcpy(v,vv,sizeof(int)*n);
		}
		rep(k,0,n) pp[i][k]=v[k];
	}
	//printf("!! %d\n",n);
	rep(i,0,n) rep(j,0,n) if (i!=j&&!vis[i][j]) {
		queue<PII> q;
		q.push(mp(i,j));
		vis[i][j]=1;
		//vector<PII> ret;
		int inv=0,tot=0;
		while (!q.empty()) {
			auto [u,v]=q.front(); q.pop();
			if (u>v) inv++;
			tot++;
			//printf("cnm %d %d\n",u,v);
			rep(w,0,M) {
				int x=pp[w][u],y=pp[w][v];
				if (!vis[x][y]) {
					q.push(mp(x,y));
					vis[x][y]=1;
				}
			}
		}
		//printf("- %d %d\n",inv,tot);
		ans=(ans+(ll)inv*(tot-inv)%mod*powmod(tot,mod-2))%mod;
	}
	printf("%lld\n",ans);
}