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
119
120
121
122
123
124
125
#include<bits/stdc++.h>
#define ll long long
#define ALL(x) begin(x), end(x)
using namespace std;

constexpr int MAXN = 3e3;
constexpr ll mod = 1e9 + 7;

ll fact[MAXN + 7];
ll factinv[MAXN + 7];

ll qp(ll a, ll b) {
    if (b == 0) return 1LL;
    ll c = qp(a, b / 2);
    c = (c * c) % mod;
    if (b % 2)
        c = (c * a) % mod;
    return c;
}

ll inv(ll x) {
    return qp(x, mod - 2);
}

ll newton(ll n, ll k) {
    if (k < 0 || k > n) return 0LL;
    return (((fact[n] * factinv[n - k]) % mod) * factinv[k]) % mod;
}

void prepro() {
    fact[0] = 1LL;
    for (ll i = 1; i <= MAXN; i++) {
        fact[i] = (fact[i - 1] * i) % mod;
        factinv[i] = inv(fact[i]);
    }
}

void add_perm(vector <int> &p1, vector <int> const& p2) {
    vector <int> r;
    for (int i = 0; i < p1.size(); i++) 
        r.push_back(p2[p1[i]]);
    swap(r, p1);
}

ll _num_inversions(vector <int> &v) {
    if (v.size() < 2) return 0LL;
    vector <int> v1, v2;
    for (int i = 0; i < v.size() / 2; i++) v1.push_back(v[i]);
    for (int i = v.size() / 2; i < v.size(); i++) v2.push_back(v[i]);
    
    ll res = _num_inversions(v1) + _num_inversions(v2);
    
    vector <int> vr;
    int p1 = 0, p2 = 0;
    
    while (p1 < v1.size() || p2 < v2.size()) {
        if (p1 == v1.size()) {
            vr.push_back(v2[p2++]);
            continue;
        }
        if (p2 == v2.size()) {
            vr.push_back(v1[p1++]);
            res += p2;
            continue;
        }

        if (v1[p1] < v2[p2]) {
            vr.push_back(v1[p1++]);
            res += p2;
        }
        else 
            vr.push_back(v2[p2++]);
    }
    swap(vr, v);
    return res;
}

ll num_inversions(vector <int> v) {
    return _num_inversions(v);
}

string vstr(vector <int> const& v) {
    string res = "";
    for (auto i : v) res += to_string(i) + " ";
    return res;
}

int main() {
    prepro();
    ll n, k;
    cin >> n >> k;

    if (k > 1) { // XD
        cout << (n * (n - 1) * inv(4)) % mod << "\n";
        return 0;
    }

    vector <int> perm(n);
    for (int i = 0; i < n; i++) {
        cin >> perm[i];
        perm[i]--;
    }

    ll num_perms = 0;
    ll sum_inv = 0;
    for (vector <int> v = perm; true; add_perm(v, perm)) {
        num_perms++;
        ll invs = num_inversions(v);
        sum_inv += invs;
        if (sum_inv > mod) sum_inv -= mod;
        if (invs == 0) break;
    }

    cout << (inv(num_perms) * sum_inv) % mod << "\n";

    /*cout << "XDDD\n";
    cout << num_perms << " " << sum_inv << "\n";

    vector <int> v = perm;
    for (int i = 0; i < 10; i++) {
        cout << vstr(v) << num_inversions(v) << "\n";
        add_perm(v, perm);
    }*/
    return 0;
}