o59_oct_c2_dslope

#include <bits/stdc++.h>

using namespace std;
using lli = long long;
const lli Mod = 1e9 - 1;
const int N = 8e4 + 10;
const int K = 40 + 10;
int ar[N];
lli dp[N][K];
int n, k;

void Upd(int i, int j, int val){
    for(int idx=i;idx<=n;idx+=idx&-idx)
        dp[idx][j] = (dp[idx][j] + (lli) val + Mod) % Mod;
}

lli Sum(int i, int j, lli sum = 0){
    for(int idx=i;idx>=1;idx-=idx&-idx)
        sum = (sum + dp[idx][j] + Mod) % Mod;
    return sum;
}

int main(){

    scanf("%d %d", &n, &k);

    for(int i=1;i<=n;i++) scanf("%d", &ar[i]);

    for(int i=1;i<=n;i++){
        Upd(ar[i], 1, 1);
        for(int j=2;j<=k;j++){
            lli sum = Sum(n, j - 1) - Sum(ar[i], j - 1);
            Upd(ar[i], j, sum);
        }
    }

    cout << Sum(n, k);

    return 0;
}