#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 4;
long long sg[4 * N], c[N];
long long query(int p, int l, int r, int i, int j) {
  if (l > j || r < i) return 0;
  if (l >= i && r <= j) return sg[p];
  int mid = (l + r) >> 1;
  return query(p * 2, l, mid, i, j) + query(p * 2 + 1, mid + 1, r, i, j);
}
long long update(int p, int l, int r, int indx, long long val) {
  if (indx < l || indx > r) return sg[p];
  if (l == r) return sg[p] = val;
  int mid = (l + r) >> 1;
  long long p1 = update(p * 2, l, mid, indx, val);
  long long p2 = update(p * 2 + 1, mid + 1, r, indx, val);
  return sg[p] = p1 + p2;
}
int main() {
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  int cnt = 0;
  for (int &x : a) cin >> x;
  fill(c + 1, c + n + 1, 1);
  for (int i = 2; i <= k + 1; ++i) {
    memset(sg, 0, sizeof sg);
    for (int j = 0; j < n; ++j) {
      update(1, 0, n, a[j], c[a[j]]);
      c[a[j]] = query(1, 0, n, 0, a[j] - 1);
    }
  }
  long long ans = accumulate(c, c + n + 1, 0ll);
  cout << ans << '\n';
  return 0;
}
