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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const LL MOD = 1e9 + 7;

LL getNumOfInversions(vector<int>& A) {
	LL N = A.size();
	if (N <= 1) {
		return 0;
	}
	priority_queue<pair<LL, LL>, vector<pair<LL, LL>>, greater<pair<LL, LL>>> sortList;
	LL result = 0;

	for (LL i = 0; i < N; i++) {
		sortList.push(make_pair(A[i], i));
	}
	vector<int> x;
	while (!sortList.empty()) {
		LL i = sortList.top().second;
		sortList.pop();
		LL y = upper_bound(x.begin(), x.end(), i) - x.begin();
		result += i - y;

		x.insert(upper_bound(x.begin(), x.end(), i), i);
	}

	return result;
}

LL gcd(LL a, LL b, LL& x, LL& y) {
	x = 1, y = 0;
	LL x1 = 0, y1 = 1, a1 = a, b1 = b;
	while (b1) {
		LL q = a1 / b1;
		tie(x, x1) = make_tuple(x1, x - q * x1);
		tie(y, y1) = make_tuple(y1, y - q * y1);
		tie(a1, b1) = make_tuple(b1, a1 - q * b1);
	}
	return a1;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	LL n, k;
	cin >> n >> k;
	set<vector<int>> s;
	vector<vector<int>> vv;
	for (LL i = 0; i < k; i++) {
		vector<int> v(n);
		for (LL j = 0; j < n; j++) {
			cin >> v[j];
			v[j]--;
		}
		if(s.find(v) == s.end()){
			s.insert(v);
			vv.push_back(v);
		}
	}
	k = vv.size();
	for (LL l = 0; l < k; l++)
	for (LL lq = 0; lq < k; lq++)
		for (LL ll = 0; ll < k; ll++)
			for (LL i = 0; i < k; i++) {
				unsigned id = 0;
				while (id < vv.size()) {
					while (true) {
						vector<int> v(n);
						for (LL j = 0; j < n; j++) {
							v[j] = vv[i][vv[id][j]];
						}
						if (s.find(v) == s.end()) {
							vv.push_back(v);
							s.insert(v);
						} else {
							id++;
							break;
						}
					}
				}
			}
	LL p = 0;
	for (auto& v : vv) {
		p += getNumOfInversions(v);
	}
	LL q = vv.size();
	LL g = gcd(p, q);
	p /= g;
	q /= g;

	LL x, y;
	LL gg = gcd(q, MOD, x, y);

	if (gg != 1) {
		cout << p % MOD << "\n";
	} else {
		LL xx = (x % MOD + MOD) % MOD;
		LL pp = p % MOD;
		cout << (pp * xx) % MOD << "\n";
	}

	return 0;
}