#include <bits/stdc++.h>
#pragma GCC optimize("O2")
using namespace std;
inline long long int input() {
  long long int n;
  cin >> n;
  return n;
}
long long int pw(long long int a, long long int b) {
  return (!b ? 1 : (b & 1 ? a * pw(a * a, b / 2) : pw(a * a, b / 2)));
}
const long long int MAXN = 1e6 + 10;
const long long int MAXA = 101;
const long long int INF = 8e18;
const long long int MOD = 1e9 + 7;
const long double PI = 4 * atan((long double)1);
long long int fen[MAXN][15];
void add(long long int ind, long long int ind2, long long int val) {
  for (long long int i = ind2; i < MAXN; i += (i & (-i))) fen[i][ind] += val;
}
long long int get(long long int k, long long int ind) {
  long long int sum = 0;
  for (long long int i = ind; i; i -= (i & (-i))) sum += fen[i][k];
  return sum;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  ;
  mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  ;
  long long int n, k;
  cin >> n >> k;
  k++;
  for (long long int i = 1; i <= n; i++) {
    long long int x;
    cin >> x;
    for (long long int j = k; j >= 2; j--) {
      add(j, x, get(j - 1, x - 1));
    }
    add(1, x, 1);
  }
  return cout << get(k, MAXN - 1) << endl, 0;
  ;
  return 0;
}
