#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 7;
long long tree[12][4 * MAXN];
int a[MAXN];
void update(int k, int on, int st, int end, int id, long long val) {
  if (st > id || end < id) return;
  if (st == id && end == id) {
    tree[k][on] += val;
    return;
  }
  int mid = (st + end) >> 1;
  update(k, on << 1, st, mid, id, val);
  update(k, on << 1 | 1, mid + 1, end, id, val);
  tree[k][on] = tree[k][on << 1] + tree[k][on << 1 | 1];
}
long long query(int k, int on, int st, int end, int l, int r) {
  if (st > r || end < l) return 0;
  if (st >= l && end <= r) {
    return tree[k][on];
  }
  int mid = (st + end) >> 1;
  return query(k, on << 1, st, mid, l, r) +
         query(k, on << 1 | 1, mid + 1, end, l, r);
}
int main() {
  int n, K;
  cin >> n >> K;
  K++;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  for (int i = 1; i <= n; i++) {
    update(1, 1, 1, n, a[i], 1);
    for (int j = 2; j <= K; j++) {
      long long q = query(j - 1, 1, 1, n, 0, a[i] - 1);
      update(j, 1, 1, n, a[i], q);
    }
  }
  cout << query(K, 1, 1, n, 1, n);
  return 0;
}

### Prompt

Generate 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>
using namespace std;
const int MAXN = 1e5 + 7;
long long tree[12][4 * MAXN];
int a[MAXN];
void update(int k, int on, int st, int end, int id, long long val) {
  if (st > id || end < id) return;
  if (st == id && end == id) {
    tree[k][on] += val;
    return;
  }
  int mid = (st + end) >> 1;
  update(k, on << 1, st, mid, id, val);
  update(k, on << 1 | 1, mid + 1, end, id, val);
  tree[k][on] = tree[k][on << 1] + tree[k][on << 1 | 1];
}
long long query(int k, int on, int st, int end, int l, int r) {
  if (st > r || end < l) return 0;
  if (st >= l && end <= r) {
    return tree[k][on];
  }
  int mid = (st + end) >> 1;
  return query(k, on << 1, st, mid, l, r) +
         query(k, on << 1 | 1, mid + 1, end, l, r);
}
int main() {
  int n, K;
  cin >> n >> K;
  K++;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  for (int i = 1; i <= n; i++) {
    update(1, 1, 1, n, a[i], 1);
    for (int j = 2; j <= K; j++) {
      long long q = query(j - 1, 1, 1, n, 0, a[i] - 1);
      update(j, 1, 1, n, a[i], q);
    }
  }
  cout << query(K, 1, 1, n, 1, n);
  return 0;
}

```