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
#include <cstdio>
#include <set>
#include <vector>
using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define VAR(v,w) __typeof(w) v=(w)
#define FORE(it,c) for(VAR(it,(c).begin());it!=(c).end();++it)
#define ALL(c) (c).begin(),(c).end()
#define SIZE(c) ((int)(c).size())
#define INT(x) int x; scanf("%d", &x)

typedef long long LL;
typedef vector<int> VI;

const int mod = 1000000007;

inline LL MODL(LL a, LL b) {
	return a >= 0 ? a % b : b + ((a + 1) % b) - 1;
}

LL EXTEUC(LL a, LL b, LL& x, LL& y) {
	x = 1;
	y = 0;
	LL x1 = 0, y1 = 1;
	while (b != 0) {
		LL t = b;
		LL q = a / b;
		b = a % b;
		a = t;
		t = x1;
		x1 = x - q * x1;
		x = t;
		t = y1;
		y1 = y - q * y1;
		y = t;
	}
	return a;
}

LL REVM(LL a, LL m) {
	LL x, y;
	EXTEUC(m, a, x, y);
	return MODL(y, m);
}

VI comp(const VI& p1, const VI& p2) {
	int n = SIZE(p1);
	VI p(n);
	REP(i,n) p[i] = p1[p2[i]];
	return p;
}

int main() {
	INT(n);
	INT(k);
	set<VI> s0;
	REP(j,k) {
		VI p(n);
		REP(i,n) scanf("%d", &p[i]);
		REP(i,n) --p[i];
		s0.insert(p);
	}
	set<VI> s(ALL(s0));
	while (true) {
		VI p;
		bool good = 0;
		FORE(it,s) {
			FORE(jt,s0) {
				p = comp(*it, *jt);
				if (s.find(p) == s.end()) {
					good = true;
					break;
				}
			}
			if (good) break;
		}
		if (good) s.insert(p);
		else break;
	}
	int a = 0, b = 0;
	FORE(it,s) {
		int inv = 0;
		REP(i,n) FOR(j,i+1,n) if ((*it)[i] > (*it)[j]) ++inv;
		a += inv;
		++b;
	}
	a = MODL(a, mod);
	b = MODL(b, mod);
	int r = MODL(a * REVM(b, mod), mod);
	printf("%d\n", r);
}