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
// source: https://github.com/ShahjalalShohag/code-library/blob/main/Miscellaneous/Schreier%E2%80%93Sims%20algorithm.cpp
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define FOR(i,l,r)for(int i=(l);i<=(r);++i)
#define REP(i,n)FOR(i,0,(n)-1)
#define ssize(x)int(x.size())
#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif

#define V(x, y) n*(x) + (y)

const ll mod = 1e9 + 7;

ll fast_exp(ll a, ll x) {
	if (x == 0) {
		return 1;
	}
	if (x & 1) {
		return fast_exp(a, x-1) * a % mod;
	}
	ll res = fast_exp(a, x / 2);
	return res * res % mod;
}

struct DSU {
	int n;
	vector<int> rep;
	vector<int> ss;
	vector<int> up;
	vector<int> dwn;

	DSU(int _n) {
		n = _n;
		rep.resize(n*n);
		ss.resize(n*n);
		up.resize(n*n);
		dwn.resize(n*n);
		REP(i, n*n) {
			rep[i] = i;
			ss[i] = 1;
		}
	}

	int find_rep(int a) {
		return (a == rep[a]) ? a : rep[a] = find_rep(rep[a]);
	}

	void union_rep(int a, int b) {
		a = find_rep(a);
		b = find_rep(b);
		if (a == b) {
			return;
		}
		if (ss[a] < ss[b]) {
			swap(a, b);
		}
		rep[b] = a;
		ss[a] += ss[b];
	}

	void calculate() {
		REP(i, n) {
			REP(j, n) {
				int x = find_rep(V(i, j));
				if (i < j) {
					up[x]++;
				}
				else {
					dwn[x]++;
				}
			}
		}

		ll res = 0;
		REP(i, n*n) {
			// debug(i, up[i], dwn[i]);
			res = (res + up[i] * dwn[i] % mod * fast_exp(dwn[i] + up[i] % mod, mod-2)) % mod;
		}
		cout << res << "\n";
	}
};

int main() {
	ios_base::sync_with_stdio(0);
	int n, k;
	cin >> n >> k;
	DSU dsu(n);
	vector<int> perm(n);
	REP(i, k) {
		for (int &v : perm) {
			cin >> v;
			v--;
		}
		REP(j, n) {
			REP(l, n) {
				dsu.union_rep(V(j, l), V(perm[j], perm[l]));
			}
		}
	}
	dsu.calculate();
}