Untitled

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
// using namespace std;

template <typename T>
using o_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define ll long long
#define all(x) (x).begin(), (x).end()
#define f(i, n) for (int i = 0; i < n; i++)
#define trace(x) cerr << #x << ": " << x << '\n'
const int N = 20002, mod = 1e9;

int C[N][N], fact[N], n, k;
void prec()
{ // O(n^2)
    for (int i = 0; i < N; i++)
    {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; j++)
        {
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
        }
    }
    fact[0] = 1;
    for (int i = 1; i < N; i++)
    {
        fact[i] = 1LL * fact[i - 1] * i % mod;
    }
}

int nCr(int n, int r)
{ // O(1)
    if (n < r)
        return 0;
    return C[n][r];
}

int nPr(int n, int r)
{ // O(1)
    if (n < r)
        return 0;
    return 1LL * nCr(n, r) * fact[r] % mod;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> k;
    prec();
    vector<int> v(n + 1), dp(n + 1, 0ll);
    for (int i = 1; i <= n; i++)
        cin >> v[i];
    ll ans = 0;
    o_set<int> se;
    for (int i = 1; i <= n; i++)
    {
        int big = 0;
        big=i-1-(se.order_of_key(v[i]));
        // for (int j = 1; j < i; j++)
        // {
        //     big += v[j] > v[i];
        // }
        if (big >= k - 1)
            ans += nCr(big, k - 1);
        if (ans >= mod)
            ans -= mod;
        se.insert(v[i]);
    }
    cout << ans << "\n";
}