#include <bits/stdc++.h>
using namespace std;
const long double pi = acos(-1);
const double PI = acos(-1.);
const int N = 2e5 + 10;
int a[N];
int n;
long long tree[15][4 * N];
void build(int k, int node = 1, int st = 1, int en = n) {
  if (st == en) {
    tree[k][node] = 0;
    return;
  }
  int mid = (st + en) / 2;
  build(k, 2 * node, st, mid);
  build(k, 2 * node + 1, mid + 1, en);
  tree[k][node] = tree[k][2 * node] + tree[k][2 * node + 1];
}
void update(int k, int pos, long long val, int node = 1, int st = 1,
            int en = n) {
  if (st > pos || en < pos) return;
  if (st == pos && en == pos) {
    tree[k][node] = val;
    return;
  }
  int mid = (st + en) / 2;
  update(k, pos, val, 2 * node, st, mid);
  update(k, pos, val, 2 * node + 1, mid + 1, en);
  tree[k][node] = tree[k][2 * node] + tree[k][2 * node + 1];
}
long long query(int k, int l, int r, int node = 1, int st = 1, int en = n) {
  if (st > r || en < l) return 0;
  if (st >= l && en <= r) return tree[k][node];
  int mid = (st + en) / 2;
  long long res1 = query(k, l, r, 2 * node, st, mid);
  long long res2 = query(k, l, r, 2 * node + 1, mid + 1, en);
  return res1 + res2;
}
long long C[100005][14];
int main() {
  ios_base::sync_with_stdio(false);
  int k;
  cin >> n >> k;
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int i = 0; i <= k; i++) build(i);
  for (int i = 1; i <= n; i++) {
    update(0, a[i], 1);
    for (int d = 1; d <= k; d++) {
      long long res = 0;
      if (a[i] != 1) res = query(d - 1, 1, a[i] - 1);
      update(d, a[i], res);
    }
  }
  long long res = query(k, 1, n);
  cout << res << "\n";
  return 0;
}

### Prompt

Please create a solution in CPP 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 long double pi = acos(-1);
const double PI = acos(-1.);
const int N = 2e5 + 10;
int a[N];
int n;
long long tree[15][4 * N];
void build(int k, int node = 1, int st = 1, int en = n) {
  if (st == en) {
    tree[k][node] = 0;
    return;
  }
  int mid = (st + en) / 2;
  build(k, 2 * node, st, mid);
  build(k, 2 * node + 1, mid + 1, en);
  tree[k][node] = tree[k][2 * node] + tree[k][2 * node + 1];
}
void update(int k, int pos, long long val, int node = 1, int st = 1,
            int en = n) {
  if (st > pos || en < pos) return;
  if (st == pos && en == pos) {
    tree[k][node] = val;
    return;
  }
  int mid = (st + en) / 2;
  update(k, pos, val, 2 * node, st, mid);
  update(k, pos, val, 2 * node + 1, mid + 1, en);
  tree[k][node] = tree[k][2 * node] + tree[k][2 * node + 1];
}
long long query(int k, int l, int r, int node = 1, int st = 1, int en = n) {
  if (st > r || en < l) return 0;
  if (st >= l && en <= r) return tree[k][node];
  int mid = (st + en) / 2;
  long long res1 = query(k, l, r, 2 * node, st, mid);
  long long res2 = query(k, l, r, 2 * node + 1, mid + 1, en);
  return res1 + res2;
}
long long C[100005][14];
int main() {
  ios_base::sync_with_stdio(false);
  int k;
  cin >> n >> k;
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int i = 0; i <= k; i++) build(i);
  for (int i = 1; i <= n; i++) {
    update(0, a[i], 1);
    for (int d = 1; d <= k; d++) {
      long long res = 0;
      if (a[i] != 1) res = query(d - 1, 1, a[i] - 1);
      update(d, a[i], res);
    }
  }
  long long res = query(k, 1, n);
  cout << res << "\n";
  return 0;
}

```