#include <bits/stdc++.h>
long long md = 1000000007;
using namespace std;
template <typename T>
T pw(T a, T b) {
  T c = 1, m = a;
  while (b) {
    if (b & 1) c = (c * m);
    m = (m * m), b /= 2;
  }
  return c;
}
template <typename T>
T ceel(T a, T b) {
  if (a % b == 0)
    return a / b;
  else
    return a / b + 1;
}
template <typename T>
T my_log(T n, T b) {
  T i = 1, ans = 0;
  while (1) {
    if (i > n) {
      ans--;
      break;
    }
    if (i == n) break;
    i *= b, ans++;
  }
  return ans;
}
template <typename T>
T gcd(T a, T b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
template <typename T>
T mysqt(T a) {
  T ans = 1;
  while (ans * ans <= a) ans++;
  ans--;
  return ans;
}
long long pwmd(long long a, long long b) {
  long long c = 1, m = a;
  while (b) {
    if (b & 1) c = (c * m) % md;
    m = (m * m) % md;
    b /= 2;
  }
  return c;
}
long long modinv(long long n) { return pwmd(n, md - 2); }
long long inverse(long long i) {
  if (i == 1) return 1;
  return (md - ((md / i) * inverse(md % i)) % md + md) % md;
}
bool sortbysec(const pair<long long, long long> &a,
               const pair<long long, long long> &b) {
  return (a.second < b.second);
}
vector<char> capl = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I',
                     'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R',
                     'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'};
vector<char> sml = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i',
                    'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r',
                    's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};
template <typename T>
string conv(T a) {
  string b;
  T e = 2;
  T c = my_log(a, e);
  c++, b = '1';
  for (T i = 0; i < c - 1; i++) {
    T k = a >> (c - 2 - i);
    if (k & 1)
      b += '1';
    else
      b += '0';
  }
  if (a == 0) return "0";
  return b;
}
struct node {
  long long q = 0;
  node() {}
  node(long long val) { q = val; }
  void merge(const node &l, const node &r) { q = l.q + r.q; }
};
struct update {
  long long q = 0;
  update() {}
  update(long long val) { q = val; }
  void combine(update &other, const int32_t &tl, const int32_t &tr) {
    q = other.q;
  }
  void apply(node &x, const int32_t &tl, const int32_t &tr) {
    x.q = (tr - tl + 1) * q;
  }
};
struct segtree {
  int len;
  vector<node> t;
  vector<update> u;
  vector<bool> lazy;
  node identity_element;
  update identity_transformation;
  segtree(int l) {
    len = l;
    t.resize(4 * len);
    u.resize(4 * len);
    lazy.resize(4 * len);
    identity_element = node();
    identity_transformation = update();
  }
  void pushdown(const int32_t &v, const int32_t &tl, const int32_t &tr) {
    if (!lazy[v]) return;
    int32_t tm = (tl + tr) >> 1;
    apply(v << 1, tl, tm, u[v]);
    apply(v << 1 | 1, tm + 1, tr, u[v]);
    u[v] = identity_transformation;
    lazy[v] = 0;
  }
  void apply(const int32_t &v, const int32_t &tl, const int32_t &tr,
             update upd) {
    if (tl != tr) {
      lazy[v] = 1;
      u[v].combine(upd, tl, tr);
    }
    upd.apply(t[v], tl, tr);
  }
  template <typename T>
  void build(const T &arr, const int32_t &v, const int32_t &tl,
             const int32_t &tr) {
    if (tl == tr) {
      t[v] = arr[tl];
      return;
    }
    int32_t tm = (tl + tr) >> 1;
    build(arr, v << 1, tl, tm);
    build(arr, v << 1 | 1, tm + 1, tr);
    t[v].merge(t[v << 1], t[v << 1 | 1]);
  }
  node query(const int32_t &v, const int32_t &tl, const int32_t &tr,
             const int32_t &l, const int32_t &r) {
    if (l > tr || r < tl) {
      return identity_element;
    }
    if (tl >= l && tr <= r) {
      return t[v];
    }
    pushdown(v, tl, tr);
    int32_t tm = (tl + tr) >> 1;
    node a = query(v << 1, tl, tm, l, r),
         b = query(v << 1 | 1, tm + 1, tr, l, r), ans;
    ans.merge(a, b);
    return ans;
  }
  void rupd(const int32_t &v, const int32_t &tl, const int32_t &tr,
            const int32_t &l, const int32_t &r, const update &upd) {
    if (l > tr || r < tl) {
      return;
    }
    if (tl >= l && tr <= r) {
      apply(v, tl, tr, upd);
      return;
    }
    pushdown(v, tl, tr);
    int32_t tm = (tl + tr) >> 1;
    rupd(v << 1, tl, tm, l, r, upd);
    rupd(v << 1 | 1, tm + 1, tr, l, r, upd);
    t[v].merge(t[v << 1], t[v << 1 | 1]);
  }

 public:
  template <typename T>
  void build(const T &arr) {
    build(arr, 1, 0, len - 1);
  }
  node query(const int32_t &l, const int32_t &r) {
    return query(1, 0, len - 1, l, r);
  }
  void rupd(const int32_t &l, const int32_t &r, const update &upd) {
    rupd(1, 0, len - 1, l, r, upd);
  }
};
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  ;
  long long n, k, a;
  cin >> n >> k;
  vector<long long> v;
  for (long long i = 0; i < n; i++) cin >> a, v.push_back(a);
  if (k == 0) {
    cout << n << "\n";
    return 0;
  }
  vector<segtree> vs;
  for (long long i = 1; i < k + 2; i++) {
    segtree s(n + 1);
    vector<long long> p(n + 1, 0);
    s.build(p);
    vs.push_back(s);
  }
  long long ans = 0;
  vs[0].rupd(v[0], v[0], 1);
  for (long long i = 1; i < n; i++) {
    vs[0].rupd(v[i], v[i], 1);
    for (long long j = 2; j < k + 2; j++) {
      long long c = vs[j - 2].query(1, v[i] - 1).q;
      vs[j - 1].rupd(v[i], v[i], c);
      if (j == k + 1) ans += c;
    }
  }
  cout << ans;
}

### 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>
long long md = 1000000007;
using namespace std;
template <typename T>
T pw(T a, T b) {
  T c = 1, m = a;
  while (b) {
    if (b & 1) c = (c * m);
    m = (m * m), b /= 2;
  }
  return c;
}
template <typename T>
T ceel(T a, T b) {
  if (a % b == 0)
    return a / b;
  else
    return a / b + 1;
}
template <typename T>
T my_log(T n, T b) {
  T i = 1, ans = 0;
  while (1) {
    if (i > n) {
      ans--;
      break;
    }
    if (i == n) break;
    i *= b, ans++;
  }
  return ans;
}
template <typename T>
T gcd(T a, T b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
template <typename T>
T mysqt(T a) {
  T ans = 1;
  while (ans * ans <= a) ans++;
  ans--;
  return ans;
}
long long pwmd(long long a, long long b) {
  long long c = 1, m = a;
  while (b) {
    if (b & 1) c = (c * m) % md;
    m = (m * m) % md;
    b /= 2;
  }
  return c;
}
long long modinv(long long n) { return pwmd(n, md - 2); }
long long inverse(long long i) {
  if (i == 1) return 1;
  return (md - ((md / i) * inverse(md % i)) % md + md) % md;
}
bool sortbysec(const pair<long long, long long> &a,
               const pair<long long, long long> &b) {
  return (a.second < b.second);
}
vector<char> capl = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I',
                     'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R',
                     'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'};
vector<char> sml = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i',
                    'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r',
                    's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};
template <typename T>
string conv(T a) {
  string b;
  T e = 2;
  T c = my_log(a, e);
  c++, b = '1';
  for (T i = 0; i < c - 1; i++) {
    T k = a >> (c - 2 - i);
    if (k & 1)
      b += '1';
    else
      b += '0';
  }
  if (a == 0) return "0";
  return b;
}
struct node {
  long long q = 0;
  node() {}
  node(long long val) { q = val; }
  void merge(const node &l, const node &r) { q = l.q + r.q; }
};
struct update {
  long long q = 0;
  update() {}
  update(long long val) { q = val; }
  void combine(update &other, const int32_t &tl, const int32_t &tr) {
    q = other.q;
  }
  void apply(node &x, const int32_t &tl, const int32_t &tr) {
    x.q = (tr - tl + 1) * q;
  }
};
struct segtree {
  int len;
  vector<node> t;
  vector<update> u;
  vector<bool> lazy;
  node identity_element;
  update identity_transformation;
  segtree(int l) {
    len = l;
    t.resize(4 * len);
    u.resize(4 * len);
    lazy.resize(4 * len);
    identity_element = node();
    identity_transformation = update();
  }
  void pushdown(const int32_t &v, const int32_t &tl, const int32_t &tr) {
    if (!lazy[v]) return;
    int32_t tm = (tl + tr) >> 1;
    apply(v << 1, tl, tm, u[v]);
    apply(v << 1 | 1, tm + 1, tr, u[v]);
    u[v] = identity_transformation;
    lazy[v] = 0;
  }
  void apply(const int32_t &v, const int32_t &tl, const int32_t &tr,
             update upd) {
    if (tl != tr) {
      lazy[v] = 1;
      u[v].combine(upd, tl, tr);
    }
    upd.apply(t[v], tl, tr);
  }
  template <typename T>
  void build(const T &arr, const int32_t &v, const int32_t &tl,
             const int32_t &tr) {
    if (tl == tr) {
      t[v] = arr[tl];
      return;
    }
    int32_t tm = (tl + tr) >> 1;
    build(arr, v << 1, tl, tm);
    build(arr, v << 1 | 1, tm + 1, tr);
    t[v].merge(t[v << 1], t[v << 1 | 1]);
  }
  node query(const int32_t &v, const int32_t &tl, const int32_t &tr,
             const int32_t &l, const int32_t &r) {
    if (l > tr || r < tl) {
      return identity_element;
    }
    if (tl >= l && tr <= r) {
      return t[v];
    }
    pushdown(v, tl, tr);
    int32_t tm = (tl + tr) >> 1;
    node a = query(v << 1, tl, tm, l, r),
         b = query(v << 1 | 1, tm + 1, tr, l, r), ans;
    ans.merge(a, b);
    return ans;
  }
  void rupd(const int32_t &v, const int32_t &tl, const int32_t &tr,
            const int32_t &l, const int32_t &r, const update &upd) {
    if (l > tr || r < tl) {
      return;
    }
    if (tl >= l && tr <= r) {
      apply(v, tl, tr, upd);
      return;
    }
    pushdown(v, tl, tr);
    int32_t tm = (tl + tr) >> 1;
    rupd(v << 1, tl, tm, l, r, upd);
    rupd(v << 1 | 1, tm + 1, tr, l, r, upd);
    t[v].merge(t[v << 1], t[v << 1 | 1]);
  }

 public:
  template <typename T>
  void build(const T &arr) {
    build(arr, 1, 0, len - 1);
  }
  node query(const int32_t &l, const int32_t &r) {
    return query(1, 0, len - 1, l, r);
  }
  void rupd(const int32_t &l, const int32_t &r, const update &upd) {
    rupd(1, 0, len - 1, l, r, upd);
  }
};
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  ;
  long long n, k, a;
  cin >> n >> k;
  vector<long long> v;
  for (long long i = 0; i < n; i++) cin >> a, v.push_back(a);
  if (k == 0) {
    cout << n << "\n";
    return 0;
  }
  vector<segtree> vs;
  for (long long i = 1; i < k + 2; i++) {
    segtree s(n + 1);
    vector<long long> p(n + 1, 0);
    s.build(p);
    vs.push_back(s);
  }
  long long ans = 0;
  vs[0].rupd(v[0], v[0], 1);
  for (long long i = 1; i < n; i++) {
    vs[0].rupd(v[i], v[i], 1);
    for (long long j = 2; j < k + 2; j++) {
      long long c = vs[j - 2].query(1, v[i] - 1).q;
      vs[j - 1].rupd(v[i], v[i], c);
      if (j == k + 1) ans += c;
    }
  }
  cout << ans;
}

```