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
 99
100
101
102
#include <bits/stdc++.h>
using namespace std;
array <array<int,3001>,3001> a,b;
array<int,9000001> d,dx;
array<long long,9000001> r;
vector<array<int,2>> v;
array<int,2> q;
array<long long,31> qq,w;
int n,i,j,k,x,t,y,g,h;
long long za,zb,p,m,mh,ww,pa,pb;
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> k;
	m=1000000007;
	mh=m-2;
	for (i=0;i<=30;i++){
		qq[i]=mh%2;
		mh/=2;
	}
	/*for (i=1;i<=3000;i++){
		ww=i;
		mh=1;
		//cout << i;
		for (j=0;j<=30;j++){
			if (qq[j]){
				mh*=ww;
				mh%=m;
			}
			ww=(ww*ww)%m;
		}
		r[i]=mh;
	}
	for (i=1;i<=50;i++)
		cout << r[i] << ' ' << i << ' ' << i*r[i]%m << '\n';*/
	for (i=0;i<k;i++)
		for(j=1;j<=n;j++) {
			cin >> x;
			a[i][j]=x;
	}
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++) {
			if(i==j) continue;
			if(b[i][j]) continue;
			t++;
			v={{i,j}};
			b[i][j]=t;
			//cout << i << ' ' << j << ' ' << t << '\n';
			d[t]=1;
			if(i>j) dx[t]=1;
			x=0;
			while(x<v.size()) {
				g=v[x][0];
				h=v[x][1];
				for(y=0;y<k;y++) {
					if(b[a[y][g]][a[y][h]])
						continue;
					b[a[y][g]][a[y][h]]=t;
					d[t]++;
					if(a[y][g]>a[y][h]) dx[t]++;
					v.push_back({a[y][g],a[y][h]});
					//cout <<  a[y][g] << a[y][h] <<  d[t] << '\n';
				}
				x++;
			}
			//cout << d[t] << '\n'; 
			if(b[j][i]) continue;
			t++;
			x=0;
			for(auto q:v)
				b[q[1]][q[0]]=t;	
			d[t]=d[t-1];
			dx[t]=d[t]-dx[t-1];
			
		}
	zb=1;
	//for(i=1;i<=n;i++)
	//	for(j=1;j<=n;j++)
	//		cout << 'b' << i << ' ' << j << ' ' << b[i][j] << '\n';
	for(i=1;i<=n;i++)
		for(j=i+1;j<=n;j++) {
			p=dx[b[i][j]];
			ww=d[b[i][j]];
			za=((p*zb)%m+(za*ww)%m);
			zb=(zb*ww)%m;
			
			
		}
	ww=zb;
	mh=1;
	//cout << za <<' '<< zb <<'\n';
	for (j=0;j<=30;j++){
			if (qq[j]){
				mh*=ww;
				mh%=m;
			}
			ww=(ww*ww)%m;
		}
	cout << (za*mh)%m << '\n';
}