#include <bits/stdc++.h>
using namespace std;
long long int bit[15][100005];
long long int n;
void update(long long int row, long long int i, long long int val) {
  for (; i <= n; i += i & -i) bit[row][i] += val;
}
long long int query(long long int row, long long int i) {
  long long int sum = 0;
  for (; i > 0; i -= i & -i) sum += bit[row][i];
  return sum;
}
int main() {
  ios_base::sync_with_stdio(0);
  ;
  long long int i, j, k, x, y;
  memset(bit, 0, sizeof(bit));
  cin >> n >> k;
  for (i = 0; i < n; i++) {
    cin >> x;
    update(1, x, 1);
    for (j = 2; j < k + 2; j++) {
      y = query(j - 1, x - 1);
      update(j, x, y);
    }
  }
  cout << query(k + 1, n);
  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;
long long int bit[15][100005];
long long int n;
void update(long long int row, long long int i, long long int val) {
  for (; i <= n; i += i & -i) bit[row][i] += val;
}
long long int query(long long int row, long long int i) {
  long long int sum = 0;
  for (; i > 0; i -= i & -i) sum += bit[row][i];
  return sum;
}
int main() {
  ios_base::sync_with_stdio(0);
  ;
  long long int i, j, k, x, y;
  memset(bit, 0, sizeof(bit));
  cin >> n >> k;
  for (i = 0; i < n; i++) {
    cin >> x;
    update(1, x, 1);
    for (j = 2; j < k + 2; j++) {
      y = query(j - 1, x - 1);
      update(j, x, y);
    }
  }
  cout << query(k + 1, n);
  return 0;
}

```