#include <bits/stdc++.h>
using namespace std;
unsigned long long int div_floor(const unsigned long long int &a,
                                 const unsigned long long int &b) {
  return a / b - (((a ^ b) < 0) and a % b);
}
unsigned long long int div_ceil(const unsigned long long int &a,
                                const unsigned long long int &b) {
  return a / b + (((a ^ b) >= 0) and a % b);
}
class SegmentTreeSum {
 public:
  vector<unsigned long long int> a;
  vector<unsigned long long int> t;
  unsigned long long int n;
  SegmentTreeSum(vector<unsigned long long int> &inp) {
    a = inp;
    n = a.size();
    t.resize(4 * n);
    build(1, 0, n - 1);
  }
  SegmentTreeSum() {}
  SegmentTreeSum(unsigned long long int len) {
    n = len;
    a.resize(n, 0);
    t.resize(4 * n, 0);
  }
  SegmentTreeSum(unsigned long long int len, unsigned long long int val) {
    n = len;
    a.resize(n, val);
    t.resize(4 * n);
    build(1, 0, n - 1);
  }
  unsigned long long int left(unsigned long long int p) { return p << 1; }
  unsigned long long int right(unsigned long long int p) {
    return (p << 1) + 1;
  }
  void build(unsigned long long int v, unsigned long long int tl,
             unsigned long long int tr) {
    if (tl == tr)
      t[v] = a[tl];
    else {
      build(left(v), tl, (tl + tr) / 2);
      build(right(v), (tl + tr) / 2 + 1, tr);
      t[v] = t[left(v)] + t[right(v)];
    }
  }
  unsigned long long int rsq(unsigned long long int v,
                             unsigned long long int tl,
                             unsigned long long int tr,
                             unsigned long long int l,
                             unsigned long long int r) {
    if ((l > tr) || (r < tl)) return 0;
    if ((tl >= l) && (tr <= r)) return t[v];
    unsigned long long int p1 = rsq(left(v), tl, (tl + tr) / 2, l, r);
    unsigned long long int p2 = rsq(right(v), (tl + tr) / 2 + 1, tr, l, r);
    return p1 + p2;
  }
  void update(unsigned long long int v, unsigned long long int tl,
              unsigned long long int tr, unsigned long long int pos) {
    if (tl == tr)
      t[v] = a[tl];
    else {
      if (pos <= (tl + tr) / 2)
        update(left(v), tl, (tl + tr) / 2, pos);
      else
        update(right(v), (tl + tr) / 2 + 1, tr, pos);
      t[v] = t[left(v)] + t[right(v)];
    }
  }
  void update(unsigned long long int pos, unsigned long long int val) {
    a[pos] = val;
    update(1, 0, n - 1, pos);
  }
  unsigned long long int query(unsigned long long int l,
                               unsigned long long int r) {
    return rsq(1, 0, n - 1, l, r);
  }
  unsigned long long int val(unsigned long long int pos) { return a[pos]; }
};
void solve() {
  unsigned long long int n, k;
  cin >> n >> k;
  vector<SegmentTreeSum> trees(k + 1, SegmentTreeSum(n + 1));
  unsigned long long int answer = 0;
  for (unsigned long long int i = 0; i < n; i++) {
    unsigned long long int elem;
    cin >> elem;
    trees[0].update(elem, 1);
    for (unsigned long long int j = 1; j <= k; j++)
      trees[j].update(elem, trees[j - 1].query(0, elem - 1));
  }
  cout << trees[k].query(0, n) << '\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  unsigned long long int t = 1;
  while (t--) solve();
}
