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
#include<bits/stdc++.h>

using namespace std;

int n,k;
long long MOD = 1e9 + 7;
set<vector<int>> all_perm;
vector<vector<int>> moves;
queue<vector<int>> que;


long long fast_exp(long long a, int b){
    if(b == 1) return a;
    long long tmp = fast_exp(a,b/2);
    if(b&1){
        return (((tmp * tmp) % MOD) * a) % MOD;
    }
    return (tmp * tmp) % MOD;     
}

void f1(vector<int>& a, vector<int>& b){
    vector<int> ans(n);
    for(int i = 0; i < n; i++){
        ans[i] = a[b[i]-1];
    }
    if(all_perm.find(ans) == all_perm.end()){
        all_perm.insert(ans);
        que.push(ans);
    }
}

int f2(vector<int>& a){
    int ans = 0;
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            if(a[i] > a[j]) ans++;
        }
    }
    return ans;
}

void print_v(vector<int> a){
    for(int i : a){
        cout << i << " ";
    }
    cout << "\n";
}

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    
    cin >> n >> k;
    vector<int> tmpp(n);
    // int tmp;

    for(int i = 0; i < k; i++){
        for(int j = 0; j < n; j++){
            cin >> tmpp[j];
        }
        all_perm.insert(tmpp);
        moves.push_back(tmpp);
        que.push(tmpp);
    }

    while(!que.empty()){
        tmpp = que.front();
        que.pop();
        for(int i = 0; i < k; i++){
            f1(tmpp,moves[i]);
        }
    }

    long long sum = 0;
    for(auto i : all_perm){
        sum += f2(i);
        // print_v(i);
    }
    cout << ((sum % MOD) * fast_exp(all_perm.size(),MOD-2)) % MOD << "\n";
    return 0;
}