#include <bits/stdc++.h>
using namespace std;
long long int f(long long int a, long long int b) { return a + b; }
struct segtree {
  long long int t[4 * 100005];
  int n, identity;
  segtree(int n_ = 0) {
    identity = 0;
    n = n_;
    memset(t, 0, sizeof(long long int) * 4 * n);
  }
  long long int _update(int k, int l, int r, int x, long long int v) {
    if (x < l || r < x) {
      return t[k];
    }
    if (l == r && l == x) {
      t[k] += v;
      return t[k];
    }
    int mid = (l + r) >> 1;
    return t[k] = (_update(k << 1, l, mid, x, v) +
                   _update(k << 1 | 1, mid + 1, r, x, v));
  }
  void update(int x, long long int v) { _update(1, 0, n - 1, x, v); }
  long long int _query(int k, int l, int r, int x, int y) {
    if (y < l || r < x) {
      return identity;
    }
    if (x <= l && r <= y) {
      return t[k];
    }
    int mid = (l + r) >> 1;
    return (_query(k << 1, l, mid, x, y) +
            _query(k << 1 | 1, mid + 1, r, x, y));
  }
  long long int query(int x, int y) { return _query(1, 0, n - 1, x, y); }
} bit[12];
vector<pair<int, int> > b;
int a[100005];
int main() {
  ios_base::sync_with_stdio(0);
  int n, k, temp;
  cin >> n >> k;
  b.clear();
  for (int i = 0; i < n; ++i) {
    cin >> temp;
    b.push_back({temp, i});
  }
  sort(b.begin(), b.end());
  for (int i = 0; i < n; ++i) {
    a[b[i].second] = i + 1;
  }
  for (int i = 1; i <= k + 1; ++i) {
    bit[i] = segtree(n + 1);
  }
  for (int i = 0; i < n; ++i) {
    bit[1].update(a[i], 1);
    for (int j = 2; j <= k + 1; ++j) {
      bit[j].update(a[i], bit[j - 1].query(1, a[i] - 1));
    }
  }
  cout << bit[k + 1].query(1, n) << '\n';
  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;
long long int f(long long int a, long long int b) { return a + b; }
struct segtree {
  long long int t[4 * 100005];
  int n, identity;
  segtree(int n_ = 0) {
    identity = 0;
    n = n_;
    memset(t, 0, sizeof(long long int) * 4 * n);
  }
  long long int _update(int k, int l, int r, int x, long long int v) {
    if (x < l || r < x) {
      return t[k];
    }
    if (l == r && l == x) {
      t[k] += v;
      return t[k];
    }
    int mid = (l + r) >> 1;
    return t[k] = (_update(k << 1, l, mid, x, v) +
                   _update(k << 1 | 1, mid + 1, r, x, v));
  }
  void update(int x, long long int v) { _update(1, 0, n - 1, x, v); }
  long long int _query(int k, int l, int r, int x, int y) {
    if (y < l || r < x) {
      return identity;
    }
    if (x <= l && r <= y) {
      return t[k];
    }
    int mid = (l + r) >> 1;
    return (_query(k << 1, l, mid, x, y) +
            _query(k << 1 | 1, mid + 1, r, x, y));
  }
  long long int query(int x, int y) { return _query(1, 0, n - 1, x, y); }
} bit[12];
vector<pair<int, int> > b;
int a[100005];
int main() {
  ios_base::sync_with_stdio(0);
  int n, k, temp;
  cin >> n >> k;
  b.clear();
  for (int i = 0; i < n; ++i) {
    cin >> temp;
    b.push_back({temp, i});
  }
  sort(b.begin(), b.end());
  for (int i = 0; i < n; ++i) {
    a[b[i].second] = i + 1;
  }
  for (int i = 1; i <= k + 1; ++i) {
    bit[i] = segtree(n + 1);
  }
  for (int i = 0; i < n; ++i) {
    bit[1].update(a[i], 1);
    for (int j = 2; j <= k + 1; ++j) {
      bit[j].update(a[i], bit[j - 1].query(1, a[i] - 1));
    }
  }
  cout << bit[k + 1].query(1, n) << '\n';
  return 0;
}

```