#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 10;
int n, k;
ll arr[N], ft[N], val[N], old[N];
void add(int i, ll x) {
  for (; i <= n; i += i & -i) ft[i] += x;
}
ll query(int i) {
  ll ans = 0;
  for (; i > 0; i -= i & -i) ans += ft[i];
  return ans;
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; ++i) {
    scanf("%I64d", &arr[i]);
    val[i] = 1;
  }
  ll sum = n;
  while (k--) {
    for (int i = 1; i <= n; ++i) {
      ft[i] = 0;
      old[i] = val[i];
    }
    sum = 0;
    for (int i = 1; i <= n; ++i) {
      val[i] = query(arr[i]);
      sum += val[i];
      add(arr[i] + 1, old[i]);
    }
  }
  printf("%I64d", sum);
  return 0;
}

### Prompt

Your challenge is to write 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;
using ll = long long;
const int N = 1e5 + 10;
int n, k;
ll arr[N], ft[N], val[N], old[N];
void add(int i, ll x) {
  for (; i <= n; i += i & -i) ft[i] += x;
}
ll query(int i) {
  ll ans = 0;
  for (; i > 0; i -= i & -i) ans += ft[i];
  return ans;
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; ++i) {
    scanf("%I64d", &arr[i]);
    val[i] = 1;
  }
  ll sum = n;
  while (k--) {
    for (int i = 1; i <= n; ++i) {
      ft[i] = 0;
      old[i] = val[i];
    }
    sum = 0;
    for (int i = 1; i <= n; ++i) {
      val[i] = query(arr[i]);
      sum += val[i];
      add(arr[i] + 1, old[i]);
    }
  }
  printf("%I64d", sum);
  return 0;
}

```