#include <bits/stdc++.h>
using namespace std;
long long fen[100009][11];
void update(int i, int j, long long upd, int n) {
  while (i < n) {
    fen[i][j] += upd;
    i += ((i) & (-i));
  }
}
long long get(int i, int j) {
  long long s = 0;
  while (i > 0) {
    s += fen[i][j];
    i -= ((i) & (-i));
  }
  return s;
}
void solution() {
  int n, k, num;
  long long ans = 0;
  cin >> n >> k;
  for (int i = 0; i < n; i++) {
    cin >> num;
    update(num, 1, 1, n + 1);
    for (int j = 2; j < k + 2; j++) {
      update(num, j, get(num - 1, j - 1), n + 1);
    }
  }
  cout << get(n, k + 1);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  long long t = 1;
  while (t--) {
    solution();
  }
  return 0;
}
