#include <bits/stdc++.h>
using namespace std;
char buf[1 << 24], *p1 = buf, *p2 = buf, obuf[1 << 24], *O = obuf;
template <typename T>
void read(T &x) {
  x = 0;
  T f = 1;
  char ch =
      (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2)
           ? EOF
           : *p1++);
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch =
        (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2)
             ? EOF
             : *p1++);
  }
  while (isdigit(ch)) {
    x = (x << 3) + (x << 1) + ch - '0';
    ch =
        (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2)
             ? EOF
             : *p1++);
  }
  x *= f;
}
int read() {
  int x = 0, f = 1;
  char ch =
      (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2)
           ? EOF
           : *p1++);
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch =
        (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2)
             ? EOF
             : *p1++);
  }
  while (isdigit(ch)) {
    x = (x << 3) + (x << 1) + ch - '0';
    ch =
        (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2)
             ? EOF
             : *p1++);
  }
  return x * f;
}
template <typename T>
void print(T x) {
  if (x < 0) *O++ = '-', x = -x;
  if (x > 9) print(x / 10);
  *O++ = x % 10 + '0';
}
template <typename T>
T Abs(T x) {
  return x < 0 ? -x : x;
}
template <typename T>
T Min(T x, T y) {
  return x < y ? x : y;
}
template <typename T>
T Max(T x, T y) {
  return x > y ? x : y;
}
const int N = 1e5 + 5;
struct BIT {
  long long t[N];
  BIT() { memset(t, 0, sizeof t); }
  int limit;
  void update(int x, long long y) {
    for (; x <= limit; x += (x & -x)) t[x] += y;
  }
  long long query(int x) {
    long long res = 0;
    for (; x; x -= (x & -x)) res += t[x];
    return res;
  }
} A[20];
int n, k;
int a[N];
long long ans;
int main() {
  n = read();
  k = 1 + read();
  for (int i = 0; i <= k; ++i) A[i].limit = n;
  for (int i = 1; i <= n; ++i) read(a[i]);
  for (int i = 1; i <= n; ++i) {
    A[1].update(a[i], 1);
    for (int j = 2; j <= k; ++j) {
      long long tmp = A[j - 1].query(a[i] - 1);
      A[j].update(a[i], tmp);
      if (j == k) ans += tmp;
    }
    if (k == 1) ans++;
  }
  print(ans);
  fwrite(obuf, O - obuf, 1, stdout);
  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;
char buf[1 << 24], *p1 = buf, *p2 = buf, obuf[1 << 24], *O = obuf;
template <typename T>
void read(T &x) {
  x = 0;
  T f = 1;
  char ch =
      (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2)
           ? EOF
           : *p1++);
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch =
        (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2)
             ? EOF
             : *p1++);
  }
  while (isdigit(ch)) {
    x = (x << 3) + (x << 1) + ch - '0';
    ch =
        (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2)
             ? EOF
             : *p1++);
  }
  x *= f;
}
int read() {
  int x = 0, f = 1;
  char ch =
      (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2)
           ? EOF
           : *p1++);
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch =
        (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2)
             ? EOF
             : *p1++);
  }
  while (isdigit(ch)) {
    x = (x << 3) + (x << 1) + ch - '0';
    ch =
        (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2)
             ? EOF
             : *p1++);
  }
  return x * f;
}
template <typename T>
void print(T x) {
  if (x < 0) *O++ = '-', x = -x;
  if (x > 9) print(x / 10);
  *O++ = x % 10 + '0';
}
template <typename T>
T Abs(T x) {
  return x < 0 ? -x : x;
}
template <typename T>
T Min(T x, T y) {
  return x < y ? x : y;
}
template <typename T>
T Max(T x, T y) {
  return x > y ? x : y;
}
const int N = 1e5 + 5;
struct BIT {
  long long t[N];
  BIT() { memset(t, 0, sizeof t); }
  int limit;
  void update(int x, long long y) {
    for (; x <= limit; x += (x & -x)) t[x] += y;
  }
  long long query(int x) {
    long long res = 0;
    for (; x; x -= (x & -x)) res += t[x];
    return res;
  }
} A[20];
int n, k;
int a[N];
long long ans;
int main() {
  n = read();
  k = 1 + read();
  for (int i = 0; i <= k; ++i) A[i].limit = n;
  for (int i = 1; i <= n; ++i) read(a[i]);
  for (int i = 1; i <= n; ++i) {
    A[1].update(a[i], 1);
    for (int j = 2; j <= k; ++j) {
      long long tmp = A[j - 1].query(a[i] - 1);
      A[j].update(a[i], tmp);
      if (j == k) ans += tmp;
    }
    if (k == 1) ans++;
  }
  print(ans);
  fwrite(obuf, O - obuf, 1, stdout);
  return 0;
}

```