#include <bits/stdc++.h>
void upd(long long unsigned *B, unsigned n, long long unsigned v) {
  for (; n < 111111; n += n & -n) B[n] += v;
  return;
}
long long unsigned que(long long unsigned *B, unsigned n) {
  long long unsigned v = 0llu;
  for (; n; n &= n - 1) v += B[n];
  return v;
}
long long unsigned D[11][111111];
int main() {
  unsigned n, i, j, k;
  scanf("%u%u", &n, &k);
  while (n--) {
    scanf("%u", &i);
    for (j = 11; --j;) upd(D[j], i, que(D[j - 1], i));
    upd(D[0], i, 1);
  }
  printf("%I64u\n", que(D[k], 111110));
  return 0;
}

### Prompt

Please formulate a CPP solution to the following problem:

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>
void upd(long long unsigned *B, unsigned n, long long unsigned v) {
  for (; n < 111111; n += n & -n) B[n] += v;
  return;
}
long long unsigned que(long long unsigned *B, unsigned n) {
  long long unsigned v = 0llu;
  for (; n; n &= n - 1) v += B[n];
  return v;
}
long long unsigned D[11][111111];
int main() {
  unsigned n, i, j, k;
  scanf("%u%u", &n, &k);
  while (n--) {
    scanf("%u", &i);
    for (j = 11; --j;) upd(D[j], i, que(D[j - 1], i));
    upd(D[0], i, 1);
  }
  printf("%I64u\n", que(D[k], 111110));
  return 0;
}

```