#include <bits/stdc++.h>
using namespace std;
long long mod = 5000000;
int n;
long long BIT[51][100001];
void update(int l, int x, long long val) {
  for (int X = x; X < 100002; X += X & -X) {
    BIT[l][X] = (BIT[l][X] + val);
  }
}
long long query_sum(int x, int l) {
  long long sum = 0;
  for (int X = x; X > 0; X -= X & -X) {
    sum = (sum + BIT[l][X]);
  }
  return sum;
}
int main() {
  int K, l, r, a, p;
  scanf("%d %d", &n, &K);
  K++;
  int t = n;
  while (t--) {
    scanf("%d", &a);
    update(1, a, 1);
    for (int k = 2; k <= K; k++) {
      long long sbseqnce_wth_sz_k_minus_1_less_than_a = query_sum(a - 1, k - 1);
      update(k, a, sbseqnce_wth_sz_k_minus_1_less_than_a);
    }
  }
  long long ans = query_sum(100000, K);
  printf("%lld\n", ans);
}

### Prompt

In cpp, your task is to solve 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 mod = 5000000;
int n;
long long BIT[51][100001];
void update(int l, int x, long long val) {
  for (int X = x; X < 100002; X += X & -X) {
    BIT[l][X] = (BIT[l][X] + val);
  }
}
long long query_sum(int x, int l) {
  long long sum = 0;
  for (int X = x; X > 0; X -= X & -X) {
    sum = (sum + BIT[l][X]);
  }
  return sum;
}
int main() {
  int K, l, r, a, p;
  scanf("%d %d", &n, &K);
  K++;
  int t = n;
  while (t--) {
    scanf("%d", &a);
    update(1, a, 1);
    for (int k = 2; k <= K; k++) {
      long long sbseqnce_wth_sz_k_minus_1_less_than_a = query_sum(a - 1, k - 1);
      update(k, a, sbseqnce_wth_sz_k_minus_1_less_than_a);
    }
  }
  long long ans = query_sum(100000, K);
  printf("%lld\n", ans);
}

```