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
105
106
107
108
109
110
111
112
113
114
#include <bits/stdc++.h>
#include <cassert>
#include <ios>

#define DEBUG(x) cout << #x << " = " << x << '\n';

using namespace std;

typedef long long lld;

const lld MOD = 1e9 + 7;

lld fpw(lld x, lld k) {
  lld res = 1;
  for (; k > 0; k >>= 1) {
    if (k & 1)
      res = res * x % MOD;
    x = x * x % MOD;
  }
  return res;
}

struct frac {
  mutable lld x, y;

  void reduce() const {
    const lld d = gcd(x, y);
    x /= d, y /= d;
    x %= MOD, y %= MOD;
  }

  lld to_int() const { return x * fpw(y, MOD - 2) % MOD; }

  frac &operator+=(const frac &other) {
    other.reduce();
    x *= other.y;
    x += y * other.x;
    y *= other.y;
    reduce();
    return *this;
  }
};

int n, k;
const int MAXN = 3000;
int perms[MAXN + 1][MAXN + 1];
int comp[MAXN + 1][MAXN + 1];
int components;
int cumsize;

int counter;
void make_component(int x, int y) {
  ++components;
  comp[x][y] = components;
  ++cumsize;

  queue<pair<int, int>> q{{{x, y}}};
  while (!q.empty()) {
    auto [x, y] = q.front();
    q.pop();

    for (int i = 0; i < k; ++i) {
      const int nx = perms[i][x], ny = perms[i][y];
      if (comp[nx][ny])
        continue;
      comp[nx][ny] = components;
      ++cumsize;
      if (cumsize == n * (n - 1))
        return;
      q.push({nx, ny});
    }
  }
}

void make_connected() {
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      if (i == j || comp[i][j])
        continue;
      make_component(i, j);
    }
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> n >> k;

  for (int i = 0; i < k; ++i)
    for (int j = 0; j < n; ++j) {
      cin >> perms[i][j];
      --perms[i][j];
    }

  make_connected();

  vector<int> invs(components, 0), sz(components, 0);
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      if (i == j)
        continue;
      const int col = comp[i][j] - 1;
      ++sz[col];
      invs[col] += (i > j);
    }
  }

  frac res = {0, 1};
  for (int i = 0; i < components; ++i)
    res += frac{(lld)invs[i] * (sz[i] - invs[i]), sz[i]};
  cout << res.to_int() << '\n';
}