#include <bits/stdc++.h>
using namespace std;
typedef long long int LL;
LL t[65536][10];
LL p[10];
const int mod = 1e9;
void add (int a) {
    for (int i=0; i<10; i++)
        p[i]=(p[i]+t[a][i])%mod;
}
void calculate (int a, int b) {
    for (int i=0; i<10; i++)
        p[i]=0LL;
    while (a <= b) {
        if (a&1)
            add(a++);
        if (!(b&1))
            add(b--);
        a/=2;
        b/=2;
    }
}
void update (int a) {
    a/=2;
    while (a) {
        for (int i=0; i<10; i++)
            t[a][i]=t[a*2][i]+t[a*2+1][i];
        a/=2;
    }
}
void insert (int a, int bs, int n) {
    calculate (bs+a, bs+n-1);
    for (int i=8; i>=0; i--)
        p[i+1]=p[i];
    p[0]=1;
    for (int i=0; i<10; i++)
        t[a+bs-1][i]=p[i];
    update (bs+a-1);
}
int main () {
    int n, k, x, bs;
    scanf ("%d%d", &n, &k);
    bs=1;
    while (bs<n) bs*=2;
    for (int i=0; i<n; i++) {
        scanf ("%d", &x);
        insert (x, bs, n);
    }
    LL wyn=0;
    for (int i=bs; i<bs+n; i++)
        wyn=(wyn+t[i][k-1])%mod;
    printf ("%lld", wyn);
}