#include <bits/stdc++.h>
using namespace std;
template <class t>
inline t read(t &x) {
  char c = getchar();
  bool f = 0;
  x = 0;
  while (!isdigit(c)) f |= c == '-', c = getchar();
  while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
  if (f) x = -x;
  return x;
}
template <class t, class... A>
inline void read(t &x, A &...a) {
  read(x);
  read(a...);
}
template <class t>
inline void write(t x) {
  if (x < 0)
    putchar('-'), write(-x);
  else {
    if (x > 9) write(x / 10);
    putchar('0' + x % 10);
  }
}
const long long N = 1e5 + 5;
long long n, k, a[N], f[N][11];
struct bit {
  long long tr[N];
  void up(long long x, long long v) {
    while (x <= n) {
      tr[x] += v;
      x += (x & -x);
    }
  }
  long long que(long long x) {
    long long res = 0;
    while (x) {
      res += tr[x];
      x -= (x & -x);
    }
    return res;
  }
} o[11];
signed main() {
  read(n, k);
  for (long long i = 1; i <= n; i++) read(a[i]);
  for (long long i = 1; i <= n; i++) {
    f[i][0] = 1;
    for (long long j = 1; j <= k; j++) f[i][j] = o[j - 1].que(a[i] - 1);
    for (long long j = 0; j <= k; j++) o[j].up(a[i], f[i][j]);
  }
  write(o[k].que(n));
}

### Prompt

Generate 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>
inline t read(t &x) {
  char c = getchar();
  bool f = 0;
  x = 0;
  while (!isdigit(c)) f |= c == '-', c = getchar();
  while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
  if (f) x = -x;
  return x;
}
template <class t, class... A>
inline void read(t &x, A &...a) {
  read(x);
  read(a...);
}
template <class t>
inline void write(t x) {
  if (x < 0)
    putchar('-'), write(-x);
  else {
    if (x > 9) write(x / 10);
    putchar('0' + x % 10);
  }
}
const long long N = 1e5 + 5;
long long n, k, a[N], f[N][11];
struct bit {
  long long tr[N];
  void up(long long x, long long v) {
    while (x <= n) {
      tr[x] += v;
      x += (x & -x);
    }
  }
  long long que(long long x) {
    long long res = 0;
    while (x) {
      res += tr[x];
      x -= (x & -x);
    }
    return res;
  }
} o[11];
signed main() {
  read(n, k);
  for (long long i = 1; i <= n; i++) read(a[i]);
  for (long long i = 1; i <= n; i++) {
    f[i][0] = 1;
    for (long long j = 1; j <= k; j++) f[i][j] = o[j - 1].que(a[i] - 1);
    for (long long j = 0; j <= k; j++) o[j].up(a[i], f[i][j]);
  }
  write(o[k].que(n));
}

```