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
115
116
117
118
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;
using ld = long double;

//#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;

// fiind o baza, ma astept ca orice endpoint sa fie echiprobabil, so long e accesibil
// si teoretic inv(p) trebuie sa apartina G pentru orice p care e baza initiala
// nu??
// toata matematica asta deriva din adamant spunand "e fix la fel ca o baza liniara doar ca gen, are alte conditii mai muiste, dar e acelasi lucru dw"
// deci desi graful e orientat, mereu pot construi muchia inversa

const int mod = 1e9 + 7;
struct Mint {
  int val;
  Mint(ll x = 0): val((x % mod + mod) % mod) {;}
  Mint operator +(const Mint& x) { return Mint(val + x.val); }
  Mint operator -(const Mint& x) { return Mint(val - x.val); }
  Mint operator *(const Mint& x) { return Mint((ll)val * x.val); }
  Mint operator +=(const Mint& x) { return *this = Mint(val + x.val); }
  Mint operator -=(const Mint& x) { return *this = Mint(val - x.val); }
  Mint operator *=(const Mint& x) { return *this = Mint((ll)val * x.val); }
  Mint operator ^(const int& _b) const {
    Mint accum = 1, a = *this;
    int b = _b;
    while(b) {
      accum = (b & 1? accum * a : accum);
      a *= a;
      b >>= 1;
    }
    return accum;
  }
  Mint operator /(const Mint& x) { return Mint((ll)val * (x ^ (mod - 2)).val); }
  Mint operator /=(const Mint& x) { return *this = Mint((ll)val * (x ^ (mod - 2)).val); }
};

namespace DSU {
  vector<int> dsu;
  vector<int> small;
  void init(int n) {
    dsu.assign(n, -1);
    small.assign(n, 0);
  }
  int f(int x) { return dsu[x] < 0? x : dsu[x] = f(dsu[x]); }
  void unite(int x, int y) {
    x = f(x);
    y = f(y);
    
    if(x == y) return;
    //if(-dsu[x] < -dsu[y]) swap(x, y);
    
    small[x] += small[y];
    dsu[x] += dsu[y];
    dsu[y] = x;
    return;
  }
}

int n;

int f(int a, int b) {
  return (a - 1) * (n - 1) + b - 1 - (b >= a);
}

const int nmax = 3e3 + 5;
int inverse[nmax * nmax];

signed main() {
  cin.tie(0) -> sync_with_stdio(0);
  int k;
  cin >> n >> k;
  
  inverse[1] = 1;
  for(int i = 2; i < n * (n - 1) + 2; i++)
    inverse[i] = (ll)inverse[mod % i] * (mod - mod / i) % mod;
  
  DSU::init(n * (n - 1));
  
  for(int i = 1; i <= n; i++) {
    for(int j = 1; j < i; j++) {
      DSU::small[f(i, j)]++;
    }
  }
  
  for(int tc = 0; tc < k; tc++) {
    vector<int> v(n + 1);
    for(auto &x : v | views::drop(1)) cin >> x;
    for(int i = 1; i <= n; i++) {      
      for(int j = 1; j < i; j++) {
        DSU::unite(f(i, j), f(v[i], v[j]));
      }     
      for(int j = i + 1; j <= n; j++) {
        DSU::unite(f(i, j), f(v[i], v[j]));
      }
    }
  }
  
  ll sum = 0;
  for(int i = 0; i < n * (n - 1); i++) {
    if(DSU::f(i) == i)
      sum += (ll)(-DSU::dsu[i] - DSU::small[i]) * DSU::small[i] % mod * inverse[-DSU::dsu[i]] % mod;
  }
  
  cout << sum % mod << '\n';
  
}

/**
  Anul asta nu se da centroid
  -- Rugaciunile mele
*/