#include <bits/stdc++.h>
using namespace std;
int arr[100005];
long long tree[400005][13];
void update(int i, int L, int R, int node, long long val, int k) {
  if (L == R) {
    tree[i][k] = val;
    return;
  }
  if (node <= (L + R) / 2)
    update(i * 2 + 1, L, (L + R) / 2, node, val, k);
  else
    update(i * 2 + 2, (L + R) / 2 + 1, R, node, val, k);
  tree[i][k] = tree[i * 2 + 1][k] + tree[i * 2 + 2][k];
}
long long query(int i, int L, int R, int x, int y, int k) {
  if (L >= x && R <= y) return tree[i][k];
  if (L > y || R < x) return 0;
  return query(i * 2 + 1, L, (L + R) / 2, x, y, k) +
         query(i * 2 + 2, (L + R) / 2 + 1, R, x, y, k);
}
int main() {
  int n, k;
  scanf("%d %d", &n, &k);
  for (int i = 0; i < n; i++) {
    scanf("%d", &arr[i]);
    arr[i]--;
  }
  long long res = 0;
  for (int i = 0; i < n; i++) {
    update(0, 0, n - 1, arr[i], 1, 1);
    if (!k) res++;
    if (!arr[i]) continue;
    for (int j = 1; j <= k; j++) {
      long long tmp = query(0, 0, n - 1, 0, arr[i] - 1, j);
      update(0, 0, n - 1, arr[i], tmp, j + 1);
      if (j == k) res += tmp;
    }
  }
  printf("%I64d", res);
  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>
using namespace std;
int arr[100005];
long long tree[400005][13];
void update(int i, int L, int R, int node, long long val, int k) {
  if (L == R) {
    tree[i][k] = val;
    return;
  }
  if (node <= (L + R) / 2)
    update(i * 2 + 1, L, (L + R) / 2, node, val, k);
  else
    update(i * 2 + 2, (L + R) / 2 + 1, R, node, val, k);
  tree[i][k] = tree[i * 2 + 1][k] + tree[i * 2 + 2][k];
}
long long query(int i, int L, int R, int x, int y, int k) {
  if (L >= x && R <= y) return tree[i][k];
  if (L > y || R < x) return 0;
  return query(i * 2 + 1, L, (L + R) / 2, x, y, k) +
         query(i * 2 + 2, (L + R) / 2 + 1, R, x, y, k);
}
int main() {
  int n, k;
  scanf("%d %d", &n, &k);
  for (int i = 0; i < n; i++) {
    scanf("%d", &arr[i]);
    arr[i]--;
  }
  long long res = 0;
  for (int i = 0; i < n; i++) {
    update(0, 0, n - 1, arr[i], 1, 1);
    if (!k) res++;
    if (!arr[i]) continue;
    for (int j = 1; j <= k; j++) {
      long long tmp = query(0, 0, n - 1, 0, arr[i] - 1, j);
      update(0, 0, n - 1, arr[i], tmp, j + 1);
      if (j == k) res += tmp;
    }
  }
  printf("%I64d", res);
  return 0;
}

```