K-inversions

#include <bits/stdc++.h>

using namespace std;

const long long mod = 1e9;

int n, k;
vector<int> a;
vector<vector<long long>> tree;
long long res;

void update(int level, int v, int tl, int tr, int pos, long long x) {
    if (tl == tr) {
        tree[level][v] += x;
    } else {
        int tm = (tl + tr) / 2;
        if (pos <= tm) {
            update(level, v * 2, tl, tm, pos, x);
        } else {
            update(level, v * 2 + 1, tm + 1, tr, pos, x);
        }
        tree[level][v] = tree[level][v * 2] + tree[level][v * 2 + 1];
    }
    tree[level][v] %= mod;
}

long long sum(int level, int v, int tl, int tr, int l, int r) {
    if (l > r) {
        return 0;
    }
    if (tl == l && r == tr) {
        return tree[level][v];
    }
    int tm = (tl + tr) / 2;
    return (sum(level, v * 2, tl, tm, l, min(r, tm)) + sum(level, v * 2 + 1, tm + 1, tr, max(tm + 1, l), r)) % mod;
}

int main() {
    cin >> n >> k;

    a.resize(n, 0);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    tree.resize(k, vector<long long> (4 * n + 1, 0));

    for (int i = 0; i < n; ++i) {
        long long val = 1;
        for (int j = 0; j + 1 < k; ++j) {
            long long cur = sum(j, 1, 1, n, a[i] + 1, n);
            update(j, 1, 1, n, a[i], +val);
            val = cur;
            if (j == k - 2) {
                res += cur;
                res %= mod;
            }
        }
    }

    cout << res;
    return 0;
}