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

using namespace std;

#define ALL(x) (x).begin(), (x).end()

template<class C> void mini(C &a5, C b5) { a5 = min(a5, b5); }
template<class C> void maxi(C &a5, C b5) { a5 = max(a5, b5); }

// #ifdef LOCAL
// const bool debug = true;
// #else
// const bool debug = false;
// #define cerr if (true) {} else cout
// #endif
// clang-format on

// #define int long long
#define double long double

// const int INF = 1e18;
const int mod = 1e9 + 7;
const int nax = 3010;
int fu[nax * nax], fu_inv[nax * nax], fu_size[nax * nax];
int perm[nax];

int f(int x) {
    if (fu[x] == x)
        return x;
    return fu[x] = f(fu[x]);
}

void u(int x, int y) {
    x = f(x);
    y = f(y);
    if (x != y) {
        if (fu_size[x] > fu_size[y])
            swap(x, y);
        fu_inv[y] += fu_inv[x];
        fu_size[y] += fu_size[x];
        fu[x] = y;
    }
}

inline int encode(int x, int y) { return x * nax + y; }

long long pow(long long n, int k = mod - 2) {
    long long ans = 1;
    while (k) {
        if (k & 1)
            ans = ans * n % mod;
        n = n * n % mod;
        k >>= 1;
    }
    return ans;
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, k;
    cin >> n >> k;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            int e = encode(i, j);
            fu[e] = e;
            fu_inv[e] = (j < i);
            fu_size[e] = 1;
        }
    }

    while (k--) {
        for (int i = 1; i <= n; i++)
            cin >> perm[i];

        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                u(encode(i, j), encode(perm[i], perm[j]));
    }

    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            int e = encode(i, j);
            e = f(e);
            ans += fu_inv[e] * pow(fu_size[e]);
            ans %= mod;
            // cerr << i << " " << j << " " << fu_inv[e] << " " << fu_size[e] << '\n';
        }
    }

    cout << ans << '\n';

    return 0;
} /*

 */