#include <bits/stdc++.h>
using namespace std;
using T = tuple<int, int, int>;
string to_string(string s) { return '"' + s + '"'; }
string to_string(char s) { return string(1, s); }
string to_string(const char* s) { return to_string((string)s); }
string to_string(bool b) { return (b ? "true" : "false"); }
template <typename A>
string to_string(A);
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A>
string to_string(A v) {
  bool f = 1;
  string r = "{";
  for (const auto& x : v) {
    if (!f) r += ", ";
    f = 0;
    r += to_string(x);
  }
  return r + "}";
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
const long long mod = 1e9 + 7;
const long long up = 1e5 + 10;
const long long MAXN = (1LL << 20) + 10;
long long dp[up][12], k;
long long n, a[up], t[4 * up][12];
void build(long long index, long long l, long long r, long long num,
           long long val) {
  if (l == r) {
    t[index][num] = val;
    dp[l][num] = val;
    return;
  }
  long long mid = (l + r) / 2;
  build(index * 2, l, mid, num, val);
  build(index * 2 + 1, mid + 1, r, num, val);
  t[index][num] = t[2 * index][num] + t[2 * index + 1][num];
}
void update(long long index, long long l, long long r, long long pos,
            long long val, long long num) {
  if (pos < l || pos > r) return;
  if (l == r) {
    t[index][num] = val;
    return;
  }
  long long mid = (l + r) / 2;
  update(index * 2, l, mid, pos, val, num);
  update(index * 2 + 1, mid + 1, r, pos, val, num);
  t[index][num] = t[2 * index][num] + t[2 * index + 1][num];
}
long long query(long long index, long long l, long long r, long long lq,
                long long rq, long long num) {
  if (l > rq || lq > r) {
    return 0;
  }
  if (lq <= l && r <= rq) {
    return t[index][num];
  }
  long long mid = (l + r) / 2;
  return (query(index * 2, l, mid, lq, rq, num) +
          query(index * 2 + 1, mid + 1, r, lq, rq, num));
}
void solve() {
  cin >> n >> k;
  for (long long i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  for (long long i = 1; i <= n; ++i) {
    dp[i][1] = 1;
    update(1, 0, n - 1, a[i], 1, 1);
    for (long long j = 2; j <= k + 1; ++j) {
      dp[i][j] = query(1, 0, n - 1, 0, a[i] - 1, j - 1);
      update(1, 0, n - 1, a[i], dp[i][j], j);
    }
  }
  long long ans = 0;
  for (long long i = k + 1; i <= n; ++i) {
    ans += dp[i][k + 1];
  }
  cout << ans << endl;
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long T;
  T = 1;
  long long t1 = 1;
  while (true) {
    solve();
    t1++;
    if (t1 > T) break;
  }
}

### 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;
using T = tuple<int, int, int>;
string to_string(string s) { return '"' + s + '"'; }
string to_string(char s) { return string(1, s); }
string to_string(const char* s) { return to_string((string)s); }
string to_string(bool b) { return (b ? "true" : "false"); }
template <typename A>
string to_string(A);
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A>
string to_string(A v) {
  bool f = 1;
  string r = "{";
  for (const auto& x : v) {
    if (!f) r += ", ";
    f = 0;
    r += to_string(x);
  }
  return r + "}";
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
const long long mod = 1e9 + 7;
const long long up = 1e5 + 10;
const long long MAXN = (1LL << 20) + 10;
long long dp[up][12], k;
long long n, a[up], t[4 * up][12];
void build(long long index, long long l, long long r, long long num,
           long long val) {
  if (l == r) {
    t[index][num] = val;
    dp[l][num] = val;
    return;
  }
  long long mid = (l + r) / 2;
  build(index * 2, l, mid, num, val);
  build(index * 2 + 1, mid + 1, r, num, val);
  t[index][num] = t[2 * index][num] + t[2 * index + 1][num];
}
void update(long long index, long long l, long long r, long long pos,
            long long val, long long num) {
  if (pos < l || pos > r) return;
  if (l == r) {
    t[index][num] = val;
    return;
  }
  long long mid = (l + r) / 2;
  update(index * 2, l, mid, pos, val, num);
  update(index * 2 + 1, mid + 1, r, pos, val, num);
  t[index][num] = t[2 * index][num] + t[2 * index + 1][num];
}
long long query(long long index, long long l, long long r, long long lq,
                long long rq, long long num) {
  if (l > rq || lq > r) {
    return 0;
  }
  if (lq <= l && r <= rq) {
    return t[index][num];
  }
  long long mid = (l + r) / 2;
  return (query(index * 2, l, mid, lq, rq, num) +
          query(index * 2 + 1, mid + 1, r, lq, rq, num));
}
void solve() {
  cin >> n >> k;
  for (long long i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  for (long long i = 1; i <= n; ++i) {
    dp[i][1] = 1;
    update(1, 0, n - 1, a[i], 1, 1);
    for (long long j = 2; j <= k + 1; ++j) {
      dp[i][j] = query(1, 0, n - 1, 0, a[i] - 1, j - 1);
      update(1, 0, n - 1, a[i], dp[i][j], j);
    }
  }
  long long ans = 0;
  for (long long i = k + 1; i <= n; ++i) {
    ans += dp[i][k + 1];
  }
  cout << ans << endl;
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long T;
  T = 1;
  long long t1 = 1;
  while (true) {
    solve();
    t1++;
    if (t1 > T) break;
  }
}

```