#include <bits/stdc++.h>
using namespace std;
long long DP[20][100010], sol, AIB[100010];
int A[100010], N, K;
long long get_sum(int poz) {
  long long sum = 0;
  for (; poz > 0; poz -= poz & (-poz)) sum = sum + AIB[poz];
  return sum;
}
void add(int poz, long long val) {
  for (; poz <= N; poz += poz & (-poz)) AIB[poz] += val;
}
int main() {
  cin >> N >> K;
  for (int i = 1; i <= N; i++) {
    cin >> A[i];
    DP[1][i] = 1;
  }
  for (int i = 2; i <= K + 1; i++) {
    memset(AIB, 0, sizeof(AIB));
    for (int j = 1; j <= N; j++) {
      DP[i][j] = get_sum(A[j]);
      add(A[j], DP[i - 1][j]);
    }
  }
  for (int i = 1; i <= N; i++) sol = sol + DP[K + 1][i];
  cout << sol << "\n";
  return 0;
}

### 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 DP[20][100010], sol, AIB[100010];
int A[100010], N, K;
long long get_sum(int poz) {
  long long sum = 0;
  for (; poz > 0; poz -= poz & (-poz)) sum = sum + AIB[poz];
  return sum;
}
void add(int poz, long long val) {
  for (; poz <= N; poz += poz & (-poz)) AIB[poz] += val;
}
int main() {
  cin >> N >> K;
  for (int i = 1; i <= N; i++) {
    cin >> A[i];
    DP[1][i] = 1;
  }
  for (int i = 2; i <= K + 1; i++) {
    memset(AIB, 0, sizeof(AIB));
    for (int j = 1; j <= N; j++) {
      DP[i][j] = get_sum(A[j]);
      add(A[j], DP[i - 1][j]);
    }
  }
  for (int i = 1; i <= N; i++) sol = sol + DP[K + 1][i];
  cout << sol << "\n";
  return 0;
}

```