#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5;
const int Mod = 1e9;
int a[N + 5], n, k, f[15][N];
void update(int k, int pos, int val){
    while(pos <= n){
        f[k][pos] = (f[k][pos] + val) % Mod;
        pos += pos & -pos;
    }
}
int get(int k, int pos){
    int sum = 0;
    while(pos > 0){
        sum = (sum + f[k][pos]) % Mod;
        pos -= pos & -pos;
    }
    return sum;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> k;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }

    for(int i = 1; i <= n; i++){
        update(1, a[i], 1);
        for(int j = k; j >= 2; j--){
            int cur = (get(j - 1, n) - get(j - 1, a[i]) + Mod) % Mod;
            update(j, a[i], cur);
        }
    }

    cout << get(k, n);
}