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
#include <iostream>
#include <vector>
#include <numeric>
#include <queue>
#include <algorithm>
using namespace std;

struct PosPair {
    int16_t i, j;
};

long long wnk_int=0, wnk_num=0, wnk_den=1;
const long long MOD = 1000000007;
void add_to_wnk(long long num, long long den) {
    __int128_t new_wnk_num = (__int128_t)wnk_num*den + (__int128_t)wnk_den*num;
    __int128_t new_wnk_den = (__int128_t)wnk_den*den;
    wnk_int += new_wnk_num / new_wnk_den;
    new_wnk_num %= new_wnk_den;
    wnk_num = (long long)(new_wnk_num % MOD);
    wnk_den = (long long)(new_wnk_den % MOD);
    long long d = gcd(wnk_num, wnk_den);
    wnk_num = (wnk_num / d);
    wnk_den = (wnk_den / d);
}

long long power(long long b, long long e) {
    if (e==0)
        return 1;
    long long half = power(b, e/2);
    half = (half * half) % MOD;
    if (e%2)
        return (half * b) % MOD;
    else
        return half;
}
long long inv(long long x) {
    return power(x, MOD-2);
}

int main() {
    wnk_num=0, wnk_den=1;
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;
    vector<vector<int16_t>> Gens2(n, vector<int16_t>(k));
    for (int i=0; i<k; i++)
        for (int j=0; j<n; j++) {
            int x;
            cin >> x;
            Gens2[x-1][i] = j; // reverse permutation
        }

    vector<vector<bool>> Visited(n, vector<bool>(n));
    vector<vector<bool>> Side(n, vector<bool>(n));

    queue<PosPair>Q;
    for (int16_t bi=0; bi<n; bi++)
        for (int16_t bj=bi+1; bj<n; bj++)
            if (!Visited[bi][bj]) {
                Visited[bi][bj] = true;
                Q.push({bi,bj});
                long long cnt_no=1, cnt_o=0;
                bool collapse = false;

                while(!Q.empty()) {
                    PosPair pp = Q.front();
                    Q.pop();

                    for (int g=0; g<k; g++) {
                        int16_t ii = Gens2[pp.i][g];
                        int16_t jj = Gens2[pp.j][g];
                        bool rev = ii > jj;
                        if (rev)
                            swap(ii, jj);
                        if (!Visited[ii][jj]) {
                            Visited[ii][jj] = true;
                            Side[ii][jj] = (Side[pp.i][pp.j] != rev);
                            if (Side[ii][jj])
                                cnt_o++;
                            else
                                cnt_no++;
                            Q.push({ii,jj});
                        }
                        else if ((Side[pp.i][pp.j]!=rev) != Side[ii][jj])
                            collapse = true;
                    }
                }

                /* cerr << "collapse=" << collapse << endl; */
                /* cerr << "cnt_no=" << cnt_no << endl; */
                /* cerr << "cnt_o=" << cnt_o << endl; */
                if (collapse)
                    add_to_wnk(cnt_o+cnt_no, 2);
                else
                    add_to_wnk(2*cnt_o*cnt_no, cnt_o+cnt_no);
            }

    /* cout << "Result = " << wnk_num << " / " << wnk_den << endl; */
    /* cerr << "wnk_int=" << wnk_int << endl; */
    /* cerr << "wnk_num=" << wnk_num << endl; */
    /* cerr << "wnk_den=" << wnk_den << endl; */
    /* cerr << inv(wnk_den) << endl; */
    cout << ((wnk_num * inv(wnk_den) + wnk_int) % MOD) << '\n';

    return 0;
}