#include <bits/stdc++.h>
using namespace std;
template <class T>
bool umin(T& a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
bool umax(T& a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
long long a, b, c, d[100007], ans, n, m, T[12][100007 * 4], rr[100007];
set<long long> s;
map<long long, long long> mk;
void upd(int x, long long y, long long z, int l, int r, int v) {
  if (l == r) {
    T[z][v] = y;
    return;
  }
  if (x <= (l + r) / 2)
    upd(x, y, z, l, (l + r) / 2, v * 2);
  else
    upd(x, y, z, (l + r) / 2 + 1, r, v * 2 + 1);
  T[z][v] = T[z][v * 2] + T[z][v * 2 + 1];
}
long long get(int x, long long y, long long z, int l, int r, int v) {
  if (x > r || y < l) return 0;
  if (x <= l && r <= y) return T[z][v];
  return get(x, y, z, l, (l + r) / 2, v * 2) +
         get(x, y, z, (l + r) / 2 + 1, r, v * 2 + 1);
}
int main() {
  cin >> n >> m;
  m++;
  for (int i = 1; i <= n; i++) cin >> d[i], s.insert(d[i]), rr[i] = 1;
  for (long long x : s) mk[x] = ++a;
  a = 0;
  if (m == 1) {
    cout << n << endl;
    return 0;
  }
  for (int j = 2; j <= m; j++) {
    for (int i = 1; i <= n; i++) {
      upd(mk[d[i]], rr[i], j, 1, n, 1);
      long long tr = get(1, mk[d[i] - 1], j, 1, n, 1);
      rr[i] = tr;
    }
  }
  for (int i = 1; i <= n; i++) ans += rr[i];
  cout << ans << endl;
  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;
template <class T>
bool umin(T& a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
bool umax(T& a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
long long a, b, c, d[100007], ans, n, m, T[12][100007 * 4], rr[100007];
set<long long> s;
map<long long, long long> mk;
void upd(int x, long long y, long long z, int l, int r, int v) {
  if (l == r) {
    T[z][v] = y;
    return;
  }
  if (x <= (l + r) / 2)
    upd(x, y, z, l, (l + r) / 2, v * 2);
  else
    upd(x, y, z, (l + r) / 2 + 1, r, v * 2 + 1);
  T[z][v] = T[z][v * 2] + T[z][v * 2 + 1];
}
long long get(int x, long long y, long long z, int l, int r, int v) {
  if (x > r || y < l) return 0;
  if (x <= l && r <= y) return T[z][v];
  return get(x, y, z, l, (l + r) / 2, v * 2) +
         get(x, y, z, (l + r) / 2 + 1, r, v * 2 + 1);
}
int main() {
  cin >> n >> m;
  m++;
  for (int i = 1; i <= n; i++) cin >> d[i], s.insert(d[i]), rr[i] = 1;
  for (long long x : s) mk[x] = ++a;
  a = 0;
  if (m == 1) {
    cout << n << endl;
    return 0;
  }
  for (int j = 2; j <= m; j++) {
    for (int i = 1; i <= n; i++) {
      upd(mk[d[i]], rr[i], j, 1, n, 1);
      long long tr = get(1, mk[d[i] - 1], j, 1, n, 1);
      rr[i] = tr;
    }
  }
  for (int i = 1; i <= n; i++) ans += rr[i];
  cout << ans << endl;
  return 0;
}

```