#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int a[MAXN];
long long c[MAXN];
int n;
inline int lowbit(int x) { return x & -x; }
void reset(int n) {
  for (int i = 1; i <= n; ++i) c[i] = 0;
}
void add(int i, long long x = 1) {
  if (i == 0) return;
  while (i <= n) {
    c[i] += x;
    i += lowbit(i);
  }
}
long long sum(int x) {
  long long ret = 0;
  while (x > 0) {
    ret += c[x];
    x -= lowbit(x);
  }
  return ret;
}
long long dp[MAXN];
int main() {
  int k;
  scanf("%d%d", &n, &k);
  reset(n);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", a + i);
    dp[i] = 1;
  }
  for (int j = 1; j <= k; ++j) {
    reset(n);
    for (int i = 1; i <= n; ++i) {
      long long tmp = dp[i];
      dp[i] = sum(a[i]);
      add(a[i], tmp);
    }
  }
  long long ans = 0;
  for (int i = 1; i <= n; ++i) ans += dp[i];
  printf("%I64d\n", ans);
  return 0;
}
