#include <bits/stdc++.h>
using namespace std;
class FenwickTree {
 private:
  vector<long long> ft;

 public:
  FenwickTree(int n) { ft.assign(n + 1, 0); }
  long long rsq(int b) {
    long long sum = 0;
    for (; b; b -= b & (-b)) sum += ft[b];
    return sum;
  }
  long long rsq(int a, int b) { return rsq(b) - (a == 1 ? 0 : rsq(a - 1)); }
  void adjust(int k, long long v) {
    for (; k < (int)ft.size(); k += k & (-k)) ft[k] += v;
  }
};
int main() {
  int n, k;
  scanf("%d%d", &n, &k);
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
  }
  vector<FenwickTree> trees(k, FenwickTree(n));
  long long ans = 0;
  for (int i = 0; i < n; i++) {
    for (int t = k; t >= 0; t--) {
      long long q = (t > 0 ? trees[t - 1].rsq(a[i]) : 1);
      if (t < k)
        trees[t].adjust(a[i], q);
      else
        ans += q;
    }
  }
  printf("%I64d", ans);
}
