#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 9, M = 50 + 9;
long long bit[M][N];
long long query(int rem, long long val) {
  long long total = 0;
  while (val) {
    total += bit[rem][val];
    val -= (val & (-val));
  }
  return total;
}
void update(int rem, int val, long long nw) {
  while (val < N) {
    bit[rem][val] += nw;
    val += (val & (-val));
  }
}
int main() {
  int n, m, x;
  cin >> n >> m;
  ++m;
  for (int i = 0; i < n; ++i) {
    cin >> x;
    update(m, x, 1);
    for (int j = 0; j < m; ++j) {
      long long cur = query(j + 1, x - 1);
      update(j, x, cur);
    }
  }
  cout << query(1, N - 1);
  return 0;
}

### Prompt

Develop a solution in cpp to the problem described below:

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 N = 2e5 + 9, M = 50 + 9;
long long bit[M][N];
long long query(int rem, long long val) {
  long long total = 0;
  while (val) {
    total += bit[rem][val];
    val -= (val & (-val));
  }
  return total;
}
void update(int rem, int val, long long nw) {
  while (val < N) {
    bit[rem][val] += nw;
    val += (val & (-val));
  }
}
int main() {
  int n, m, x;
  cin >> n >> m;
  ++m;
  for (int i = 0; i < n; ++i) {
    cin >> x;
    update(m, x, 1);
    for (int j = 0; j < m; ++j) {
      long long cur = query(j + 1, x - 1);
      update(j, x, cur);
    }
  }
  cout << query(1, N - 1);
  return 0;
}

```