kin

#include <iostream>
#include <cstdlib>
#include <iomanip>

using std::cin;
using std::cout;

int get_right(int n) { return (n + 1) * 2; }
int get_parent(int n) { return (n - 1) / 2; }

uint64_t insert_rank(uint64_t *t, int n, int i, uint64_t inc)
{
    int id = i + n - 2;

    uint64_t r = 0;

    while(id != 0)
    {
        t[id] = (t[id] + inc) % 1000000000;

        int parent = get_parent(id);

        if(id % 2 == 1)
            r += t[get_right(parent)];

        id = parent;
    }

    return r;
}

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

    int size = 1;
    while(size < n)
        size = size << 1;

    int t[n];
    uint64_t itree[2 * size - 1];
    uint64_t inv[n][k];

    for(int i = 0; i < n; i++)
    {
        for(int j = 1; j < k; j++)
        {
            inv[i][j] = 0;
        }
        inv[i][0] = 1;
    }

    for(int i = 0; i < n; i++)
    {
        cin >> t[i];
    }

    for(int len = 1; len < k; len++)
    {
        for(int i = 0; i < 2 * size - 1; i++)
            itree[i] = 0;

        for(int i = 0; i < n; i++)
        {
            inv[i][len] = insert_rank(itree, size, t[i], inv[i][len - 1]);
        }
    }

    uint64_t r = 0;
    for(int i = 0; i < n; i++)
        r = (r + inv[i][k-1]) % 1000000000;

    cout << r;
}