#include <iostream>
using namespace std;
int arr[10004],n,k;
int tree[53][100003]={0};
int dp[53][100003]={0};
int read(int k,int idx){
    int sum = 0;
    while (idx > 0){
        sum += tree[k][idx];
        sum%=5000000;
        idx -= (idx & -idx);
    }
    return sum;
}
void update(int k,int idx ,int val){
    while (idx <= 100002){
        tree[k][idx] += val;
        tree[k][idx]%=5000000;
        idx += (idx & -idx);
    }
}
int main(){
    cin>>n>>k;
    for(int i=0;i<53;i++){
        for(int e=0;e<100002;e++){
            tree[i][e]=0;
            dp[i][e]=0;
        }
    }
    for(int i=1;i<=n;i++){
        cin>>arr[i];
        arr[i]++;
    }
    arr[0]=-2;
    dp[0][0]=1;
    update(1,1,1);
    for(int i=1;i<=n;i++){
        for(int e=1;e<=k;e++){
            dp[e][i]=read(e,arr[i]);
            update(e+1,arr[i]+1,dp[e][i]);
        }
    }
    int sol=0;
    for(int i=0;i<=n;i++){
        sol+=dp[k][i];
        sol%=5000000;
    }
    cout<<sol<<endl;
}