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
#include <cstdio>
#include <set>
#include <vector>

using namespace std;

long long MOD = 1'000'000'007LL;

long long pow(long long a, long long b) {
    if (b == 1) {
        return a % MOD;
    }
    long long c = pow(a, b/2);
    c = (c * c) % MOD;
    if (b & 1) {
        c = (c * a) % MOD;
    }
    return c;
}

class Permutation {
public:
    vector<int> s;

    Permutation(const vector<int>& s) : s(s) {}

    Permutation operator*(const Permutation& other) {
        vector<int> res(s.size());
        for (int i = 0; i<s.size(); i++) {
            res[i] = s[other.s[i]];
        }
        return Permutation(res);
    }

    bool operator<(const Permutation& other) const {
        for (int i = 0; i< s.size(); i++) {
            if (s[i] != other.s[i]) {
                return s[i] < other.s[i];
            }
        }
        return false;
    }

    int count_inversions() const {
        int sum = 0;
        for (int i = 0; i<s.size(); i++) {
            for (int j = i + 1; j<s.size(); j++) {
                if (s[i] > s[j]) sum++;
            }
        }
        return sum;
    }
};

void gen(int i, int iii, int j, int jjj, vector<Permutation>& all, set<Permutation>& all_set) {

    for (int ii = i; ii < iii; ii++) {
        for (int jj = j; jj < jjj; jj++) {
            auto p = all[ii] * all[jj];
            if (!all_set.count(p)) {
                all.push_back(p);
                all_set.insert(p);
            }
        }
    }
}

int main () {
    int n, k;
    scanf("%d%d", &n, &k);
    vector<Permutation> all;
    set<Permutation> all_set;
    for (int i = 0; i<k; i++) {
        vector<int> perm;
        for (int j = 0, a; j<n; j++) {
            scanf("%d", &a);
            perm.push_back(a - 1);
        }
        auto p = Permutation(perm);
        all.push_back(p);
        all_set.insert(p);
    }
    int i = 0, j = 0, l = k;
    while (j != l) {
        if (n * ((l-j) * (l-j) + 2 * (l-j) * (j - i)) > 3'000'000) {
            printf("%lld\n", (n * (n-1) * pow(4, MOD - 2)) % MOD);
            return 0;
        }
        gen(i, j, j, l, all, all_set);
        gen(j, l, i, j, all, all_set);
        gen(j, l, j, l, all, all_set);
        i = j;
        j = l;
        l = all.size();
    }
    long long result = 0;
    for (const Permutation& perm : all) {
        result += perm.count_inversions();
    }
    result = (result * pow(all.size(), MOD - 2)) % MOD;
    printf("%lld\n", result);
    return 0;
}