INCSEQ

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#define task "INCSEQ"
using namespace std;
using ll = long long;
using ld = long double;

template<class T>
void read(T &x){
    register int c;
    x = 0;
    while((c = getchar()) && c < '0' || c > '9');
    for(; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
}

const int N = 1e4 + 2;
int n, k, a[N];
const int mod = 5e6;
int dp[50 + 2][N];

void add(int &x, int y){
    x += y;
    x %= mod;
}

struct Trie{
    Trie *child[2];
    Trie() {child[0] = child[1] = NULL;}
    int v = 0;
    void Add(int id, int lim, int x, int val){
        if(id == lim){
            add(v, val);
            return;
        }
        if(!child[(x >> id) & 1])
            child[(x >> id) & 1] = new Trie;
        child[(x >> id) & 1] -> Add(id - 1, lim, x, val);
        add(v, val);
    }
    int count(int id, int lim, int x){
        if(id == lim)
            return v;
        int ans = 0;
        if((x >> id) & 1){
            if(child[!((x >> id) & 1)])
                add(ans, child[!((x >> id) & 1)] -> v);
            if(child[(x >> id) & 1])
                add(ans, child[(x >> id) & 1] -> count(id - 1, lim, x));
            return ans;
        }
        else{
            if(child[(x >> id) & 1])
                add(ans, child[(x >> id) & 1] -> count(id - 1, lim, x));
            return ans;
        }
    }
};
vector<Trie> s(N);
vector<int> b(N);
const int Inf = 1e9 + 7;
int id[N];

void Read(){
    //cin >> n >> k;
    read(n); read(k);
    for(int i = 1; i <= n; ++i)
        //cin >> a[i];
        read(a[i]),
        id[i] = i;
}

void Compress(){
    sort(id + 1, id + n + 1, [&](const int &x, const int &y){return a[x] < a[y];});
    int l = 0;
    for(int i = 1; i <= n; ++i){
        int j = i;
        int cur = a[id[i]];
        ++l;
        while(j <= n && a[id[j]] == cur)
            a[id[j++]] = l;
        i = j - 1;
    }
}

void Solve(){
    Compress();
    fill(b.begin(), b.end(), Inf);
    int ans = 0;
    b[0] = 0;
    s[0].Add(13, -1, 0, 1);
    for(int i = 1; i <= n; ++i){
        int j = lower_bound(b.begin(), b.end(), a[i]) - b.begin();
        b[j] = min(b[j], a[i]);
        if(j >= k)
            add(ans, s[k - 1].count(13, -1, a[i] - 1));
        for(int t = 1; t <= min(j, k); ++t)
            s[t].Add(13, -1, a[i], s[t - 1].count(13, -1, a[i] - 1));
    }
    cout << ans;
}

int32_t main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0); if(fopen(task".INP", "r"))
    freopen(task".INP", "r", stdin),
    freopen(task".OUT", "w", stdout);
    Read();
    Solve();
}