#include <bits/stdc++.h>
using namespace std;
long long int tree[500000][12], arr[100005];
void build_segment_tree(long long int tree[][12], long long int node,
                        long long int a, long long int b, long long int len) {
  if (a > b) return;
  if (a == b) {
    for (long long int i = 1; i <= len; i++) {
      tree[node][i] = 0;
    }
    return;
  }
  build_segment_tree(tree, 2 * node, a, (a + b) / 2, len);
  build_segment_tree(tree, 2 * node, (a + b) / 2 + 1, b, len);
  for (long long int i = 1; i <= len; i++) {
    tree[node][i] = tree[2 * node][i] + tree[2 * node + 1][i];
  }
  return;
}
void update_segment_tree(long long int tree[][12], long long int node,
                         long long int a, long long int b, long long int start,
                         long long int end, long long int len,
                         long long int val) {
  if (a > b) return;
  if (b < start || a > end) return;
  if (a >= start && b <= end) {
    tree[node][len] += val;
    return;
  }
  update_segment_tree(tree, 2 * node, a, (a + b) / 2, start, end, len, val);
  update_segment_tree(tree, 2 * node + 1, (a + b) / 2 + 1, b, start, end, len,
                      val);
  tree[node][len] = tree[2 * node][len] + tree[2 * node + 1][len];
  return;
}
long long int query_segment_tree(long long int tree[][12], long long int node,
                                 long long int a, long long int b,
                                 long long int start, long long int end,
                                 long long int len) {
  if (a > b || b < start || a > end) return 0;
  if (a >= start && b <= end) return tree[node][len];
  long long int ans =
      query_segment_tree(tree, 2 * node, a, (a + b) / 2, start, end, len) +
      query_segment_tree(tree, 2 * node + 1, (a + b) / 2 + 1, b, start, end,
                         len);
  return ans;
}
int main() {
  long long int n, len, k, value;
  cin >> n >> len;
  for (long long int i = 1; i <= n; i++) {
    cin >> arr[i];
  }
  build_segment_tree(tree, 1, 1, n, len);
  for (long long int i = 1; i <= n; i++) {
    for (long long int length = 0; length <= len; length++) {
      value = query_segment_tree(tree, 1, 1, n, 1, arr[i] - 1, length);
      if (length == 0) {
        value = 1;
      }
      update_segment_tree(tree, 1, 1, n, arr[i], arr[i], length + 1, value);
    }
    for (long long int length = 1; length <= len; length++) {
    }
  }
  cout << tree[1][len + 1];
  return 0;
}
