#include <bits/stdc++.h>
using namespace std;
struct treap;
typedef treap *ptreap;
const unsigned long long mod = 1000000007ll;
unsigned long long k, dp[100000][11], n, m, a, ans;
ptreap tree = NULL;
struct treap {
  ptreap l, r;
  unsigned long long x, sum[11], key, index;
  treap(unsigned long long x, unsigned long long index)
      : x(x), l(NULL), r(NULL), key(rand() % mod), index(index) {
    for (int i = 0; i < k + 1; i++) sum[i] = 0;
  };
};
void fix_sum(ptreap &t) {
  if (!t) return;
  for (int i = 0; i < k + 1; i++) t->sum[i] = dp[t->index][i];
  if (t->l)
    for (int i = 0; i < k + 1; i++) t->sum[i] += t->l->sum[i];
  if (t->r)
    for (int i = 0; i < k + 1; i++) t->sum[i] += t->r->sum[i];
}
void Merge(ptreap &t, ptreap l, ptreap r) {
  if (!l || !r)
    t = l ? l : r;
  else if (l->key > r->key)
    Merge(l->r, l->r, r), t = l;
  else
    Merge(r->l, l, r->l), t = r;
  fix_sum(t);
}
void Split(ptreap t, ptreap &l, ptreap &r, unsigned long long x) {
  if (!t)
    l = r = NULL;
  else if (x < t->x)
    Split(t->l, l, t->l, x), r = t;
  else
    Split(t->r, t->r, r, x), l = t;
  fix_sum(t);
}
void Insert(ptreap &t, ptreap v) {
  if (!t)
    t = v;
  else {
    if (v->key > t->key)
      Split(t, v->l, v->r, v->x), t = v;
    else
      Insert(v->x < t->x ? t->l : t->r, v);
  }
  fix_sum(t);
}
void dp_sum(ptreap t, unsigned long long x, unsigned long long index) {
  if (!t)
    return;
  else {
    if (x < t->x)
      dp_sum(t->l, x, index);
    else {
      for (int i = 1; i < k + 1; i++)
        dp[index][i] += t->sum[i - 1] - (t->r ? t->r->sum[i - 1] : 0);
      dp_sum(t->r, x, index);
    }
  }
}
void output(ptreap &t, int level) {
  if (!t) return;
  output(t->l, level + 1);
  output(t->r, level + 1);
}
int main() {
  scanf("%I64d%I64d", &n, &k);
  for (int i = 0; i < n; i++) {
    scanf("%I64d", &a);
    dp[i][0] = 1;
    dp_sum(tree, a, i);
    Insert(tree, new treap(a, i));
  }
  for (int i = 0; i < n; i++) ans += dp[i][k];
  printf("%I64d", ans);
  return 0;
}

### Prompt

Please formulate 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;
struct treap;
typedef treap *ptreap;
const unsigned long long mod = 1000000007ll;
unsigned long long k, dp[100000][11], n, m, a, ans;
ptreap tree = NULL;
struct treap {
  ptreap l, r;
  unsigned long long x, sum[11], key, index;
  treap(unsigned long long x, unsigned long long index)
      : x(x), l(NULL), r(NULL), key(rand() % mod), index(index) {
    for (int i = 0; i < k + 1; i++) sum[i] = 0;
  };
};
void fix_sum(ptreap &t) {
  if (!t) return;
  for (int i = 0; i < k + 1; i++) t->sum[i] = dp[t->index][i];
  if (t->l)
    for (int i = 0; i < k + 1; i++) t->sum[i] += t->l->sum[i];
  if (t->r)
    for (int i = 0; i < k + 1; i++) t->sum[i] += t->r->sum[i];
}
void Merge(ptreap &t, ptreap l, ptreap r) {
  if (!l || !r)
    t = l ? l : r;
  else if (l->key > r->key)
    Merge(l->r, l->r, r), t = l;
  else
    Merge(r->l, l, r->l), t = r;
  fix_sum(t);
}
void Split(ptreap t, ptreap &l, ptreap &r, unsigned long long x) {
  if (!t)
    l = r = NULL;
  else if (x < t->x)
    Split(t->l, l, t->l, x), r = t;
  else
    Split(t->r, t->r, r, x), l = t;
  fix_sum(t);
}
void Insert(ptreap &t, ptreap v) {
  if (!t)
    t = v;
  else {
    if (v->key > t->key)
      Split(t, v->l, v->r, v->x), t = v;
    else
      Insert(v->x < t->x ? t->l : t->r, v);
  }
  fix_sum(t);
}
void dp_sum(ptreap t, unsigned long long x, unsigned long long index) {
  if (!t)
    return;
  else {
    if (x < t->x)
      dp_sum(t->l, x, index);
    else {
      for (int i = 1; i < k + 1; i++)
        dp[index][i] += t->sum[i - 1] - (t->r ? t->r->sum[i - 1] : 0);
      dp_sum(t->r, x, index);
    }
  }
}
void output(ptreap &t, int level) {
  if (!t) return;
  output(t->l, level + 1);
  output(t->r, level + 1);
}
int main() {
  scanf("%I64d%I64d", &n, &k);
  for (int i = 0; i < n; i++) {
    scanf("%I64d", &a);
    dp[i][0] = 1;
    dp_sum(tree, a, i);
    Insert(tree, new treap(a, i));
  }
  for (int i = 0; i < n; i++) ans += dp[i][k];
  printf("%I64d", ans);
  return 0;
}

```