#include <bits/stdc++.h>
const int N = 100005;
int n, K, a[N];
long long tr[N], f[15][N], res;
inline long long rd(void) {
  long long f = 1;
  char c = getchar();
  for (; !isdigit(c); c = getchar())
    if (c == '-') f = -1;
  long long x = 0;
  for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
  return x * f;
}
inline int lowbit(int i) { return i & -i; }
inline void Add(int x, long long w) {
  for (int i = x; i <= n; i += lowbit(i)) tr[i] += w;
}
inline long long Sum(int x) {
  long long sum = 0;
  for (int i = x; i > 0; i -= lowbit(i)) sum += tr[i];
  return sum;
}
int main(void) {
  n = rd(), K = rd(), K++;
  for (register int i = (1); i <= (n); i++) a[i] = rd();
  for (register int j = (1); j <= (n); j++) f[1][j] = 1;
  for (register int i = (2); i <= (K); i++) {
    memset(tr, 0, sizeof tr);
    Add(a[i - 1], f[i - 1][i - 1]);
    for (register int j = (i); j <= (n); j++) {
      f[i][j] = Sum(a[j] - 1);
      Add(a[j], f[i - 1][j]);
    }
  }
  for (register int i = (K); i <= (n); i++) res += f[K][i];
  printf("%I64d\n", res);
  return 0;
}

### Prompt

Your challenge is to write 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>
const int N = 100005;
int n, K, a[N];
long long tr[N], f[15][N], res;
inline long long rd(void) {
  long long f = 1;
  char c = getchar();
  for (; !isdigit(c); c = getchar())
    if (c == '-') f = -1;
  long long x = 0;
  for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
  return x * f;
}
inline int lowbit(int i) { return i & -i; }
inline void Add(int x, long long w) {
  for (int i = x; i <= n; i += lowbit(i)) tr[i] += w;
}
inline long long Sum(int x) {
  long long sum = 0;
  for (int i = x; i > 0; i -= lowbit(i)) sum += tr[i];
  return sum;
}
int main(void) {
  n = rd(), K = rd(), K++;
  for (register int i = (1); i <= (n); i++) a[i] = rd();
  for (register int j = (1); j <= (n); j++) f[1][j] = 1;
  for (register int i = (2); i <= (K); i++) {
    memset(tr, 0, sizeof tr);
    Add(a[i - 1], f[i - 1][i - 1]);
    for (register int j = (i); j <= (n); j++) {
      f[i][j] = Sum(a[j] - 1);
      Add(a[j], f[i - 1][j]);
    }
  }
  for (register int i = (K); i <= (n); i++) res += f[K][i];
  printf("%I64d\n", res);
  return 0;
}

```