#include <bits/stdc++.h>
using namespace std;
const int K = 15, N = 100 * 1000 + 7;
long long f[K][N];
void update(int type, int pos, long long cnt) {
  for (int j = pos; j < N; j = (j | (j + 1))) {
    f[type][j] += cnt;
  }
}
long long get(int type, int pos) {
  long long res = 0;
  for (int j = pos; j >= 0; j = (j & (j + 1)) - 1) {
    res += f[type][j];
  }
  return res;
}
void solve() {
  int n, k;
  cin >> n >> k;
  k += 1;
  vector<int> a(n);
  if (k == 0) {
    cout << 1;
    return;
  }
  for (int j = 0; j < n; ++j) {
    cin >> a[j];
  }
  update(0, 0, 1);
  long long res = 0;
  for (int i = 0; i < n; ++i) {
    for (int j = 1; j <= k; ++j) {
      update(j, a[i], get(j - 1, a[i] - 1));
    }
  }
  cout << get(k, N - 1);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.setf(ios_base::fixed);
  cout.precision(28);
  solve();
  return 0;
}
