#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second

const int MOD = 1e9, maxn = 1e5;

vector<int> sum;

void merge_sort(vector<pair<int, int> > &to_sort, vector<int> &inv, vector<int> &res, int l, int r)
{
    if(r - l == 1)
        return;
    int m = (l + r) / 2;
    merge_sort(to_sort, inv, res, l, m);
    merge_sort(to_sort, inv, res, m, r);
    vector<pair<int, int> > tmp;
    tmp.reserve(r - l + 1);
    int it1 = l, it2 = m;
    int cnt = 0;
    while(it1 < m || it2 < r)
    {
        if(it2 == r || (it1 != m && to_sort[it1] < to_sort[it2]))
        {
            tmp.push_back(to_sort[it1]);
            cnt += inv[to_sort[it1].y];
            if(cnt > MOD) cnt -= MOD;
            it1++;
        }
        else
        {
            tmp.push_back(to_sort[it2]);
            res[to_sort[it2].y] += cnt;
            if(res[to_sort[it2].y] > MOD) res[to_sort[it2].y] -= MOD;
            it2++;
        }
    }
    for(int i = l; i < r; i++)
        to_sort[i] = tmp[i - l];

}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    vector<pair<int, int> > a(n);
    vector<int> b(maxn + 1, 1);
    for(int i = 0; i < n; i++)
        cin >> a[i].x, a[i].y = i;
    reverse(a.begin(), a.end());
    for(int i = 0; i < n; i++) a[i].y = i;
    for(int i = 1; i < k; i++)
    {
        vector<pair<int, int> > ta(a);
        vector<int> tb(maxn + 1, 0);
        merge_sort(ta, b, tb, 0, n);
        b = tb;
    }
    int cnt = 0;
    for(int i = 0; i < n; i++)
    {
        cnt += b[i];
        if(cnt > MOD) cnt -= MOD;
    }
    cout << cnt;
    return 0;
}