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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
#define mod 1000000007
#define sz(x) ((int)((x).size()))
// #define int ll
// #define N 
using namespace std;
const int N=3005;
bool vis[N][N];
int a[N][N];
int n,m;
vector<pa>all;
int tot,tot1;
int fl[N],tt[N],fa[N];
int nxt[N][N];
inline int gf(int x)
{
	while (x!=fa[x]) x=fa[x]=fa[fa[x]];
	return x;
}
inline ll quickPower(ll x,ll y)
{
	ll res=1;
	while (y)
	{
		if (y&1) res=res*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return res;
}
void dfs(int x,int y)
{
	++tot;
	tot1+=(x>y);
	vis[x][y]=1;

	if (fl[x]==fl[y]&&tot==(tt[x]-1)*tt[x]
	||tot==tt[x]*tt[y]) return;

	for (int i=1;i<=m;)
	{
		if (!vis[a[x][i]][a[y][i]])
		{
			dfs(a[x][i],a[y][i]);
			if (fl[x]==fl[y]&&tot==(tt[x]-1)*tt[x]
			||tot==tt[x]*tt[y]) return;
		}
		i=min(nxt[x][i],nxt[y][i]);
	}
}
mt19937_64 rnd(time(0));
void BellaKira()
{
	n=3000,m=3000;
	cin>>n>>m;
	for (int i=1;i<=m;i++)
	{
		poly now(n+1,0);
		for (int j=1;j<=n;j++) now[j]=j;
		for (int j=1;j<=100;j++)
		{
			int x=rnd()%n+1,y=rnd()%n+1;
			swap(now[x],now[y]);
		}
		for (int j=1;j<=n;j++) a[j][i]=now[j];
		for (int j=1;j<=n;j++) cin>>a[j][i];
	}
	for (int i=m;i>=1;i--)
	{
		for (int j=1;j<=n;j++)
			if (i==m||a[j][i]!=a[j][i+1]) nxt[j][i]=i+1;
			else nxt[j][i]=nxt[j][i+1];
	}
	for (int i=1;i<=n;i++) fa[i]=i,tt[i]=1;
	for (int i=1;i<=m;i++)
	{
		for (int j=1;j<=n;j++)
		{
			int x=j,y=a[j][i];
			x=gf(x),y=gf(y);
			if (x!=y) tt[x]+=tt[y],fa[y]=x;
		}
	}

	for (int i=1;i<=n;i++) fl[i]=gf(i);
	for (int i=1;i<=n;i++) tt[i]=tt[fl[i]];

	int ans=0;
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
			if (i!=j&&!vis[i][j]) 
			{
				tot=tot1=0;
				dfs(i,j);
				ans=(ans+1ll*(tot-tot1)*tot1%mod*quickPower(tot,mod-2)%mod)%mod;
			}
	cout<<ans<<'\n';
}
signed main()
{
	IOS;
	cin.tie(0);
	int T=1;
	while (T--)
	{
		BellaKira();
	}
}
/*list:
1.mod 998244353 or 1e9+7 or ???
2.N
3.duipai shuju xingtai duoyidian
...
*/