#include <bits/stdc++.h>
using namespace std;
const int N = 1 << 17;
const int K = 16;
template <typename T>
struct fenwick_tree {
 private:
  vector<T> a;
  int n;

 public:
  void initialize(int k) {
    n = k;
    a.assign(n + 1, 0);
  }
  void initialize(T *arr, int k) {
    n = k;
    a.assign(n + 1, 0);
    int i, nxt;
    for (i = 1; i <= k; i++) {
      a[i] += arr[i];
      nxt = i + (i & (-i));
      if (nxt <= k) a[nxt] += a[i];
    }
  }
  void update(int pos, T val) {
    for (; pos <= n; pos += pos & (-pos)) a[pos] += val;
  }
  T query(int pos) {
    T ans = 0;
    for (; pos >= 1; pos -= pos & (-pos)) ans += a[pos];
    return ans;
  }
};
fenwick_tree<unsigned long long> it[K];
int n, k;
int a[N];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int i, j;
  scanf("%d %d", &n, &k);
  ++k;
  for (i = 0; i <= k; i++) it[i].initialize(n);
  for (i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    it[1].update(a[i], 1);
    for (j = 2; j <= k; j++) it[j].update(a[i], it[j - 1].query(a[i] - 1));
  }
  printf("%llu\n", it[k].query(n));
  return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

For the given sequence with n different elements find the number of increasing subsequences with k + 1 elements. It is guaranteed that the answer is not greater than 8·1018.

Input

First line contain two integer values n and k (1 ≤ n ≤ 105, 0 ≤ k ≤ 10) — the length of sequence and the number of elements in increasing subsequences.

Next n lines contains one integer ai (1 ≤ ai ≤ n) each — elements of sequence. All values ai are different.

Output

Print one integer — the answer to the problem.

Examples

Input

5 2
1
2
3
5
4


Output

7

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1 << 17;
const int K = 16;
template <typename T>
struct fenwick_tree {
 private:
  vector<T> a;
  int n;

 public:
  void initialize(int k) {
    n = k;
    a.assign(n + 1, 0);
  }
  void initialize(T *arr, int k) {
    n = k;
    a.assign(n + 1, 0);
    int i, nxt;
    for (i = 1; i <= k; i++) {
      a[i] += arr[i];
      nxt = i + (i & (-i));
      if (nxt <= k) a[nxt] += a[i];
    }
  }
  void update(int pos, T val) {
    for (; pos <= n; pos += pos & (-pos)) a[pos] += val;
  }
  T query(int pos) {
    T ans = 0;
    for (; pos >= 1; pos -= pos & (-pos)) ans += a[pos];
    return ans;
  }
};
fenwick_tree<unsigned long long> it[K];
int n, k;
int a[N];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int i, j;
  scanf("%d %d", &n, &k);
  ++k;
  for (i = 0; i <= k; i++) it[i].initialize(n);
  for (i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    it[1].update(a[i], 1);
    for (j = 2; j <= k; j++) it[j].update(a[i], it[j - 1].query(a[i] - 1));
  }
  printf("%llu\n", it[k].query(n));
  return 0;
}

```