#include <bits/stdc++.h>
using namespace std;
long long choose(long long n, long long k);
bool isprime(long long n);
long long power(long long x, long long y, long long p);
long long power(long long x, long long y);
long long tr[12][4 * 100005];
long long dp[100005][12] = {};
void upd(long long node, long long start, long long end, long long idx,
         long long val, long long j) {
  if (start == end) {
    tr[j][node] += val;
  } else {
    long long mid = (start + end) / 2;
    if (idx >= start && idx <= mid)
      upd(2 * node, start, mid, idx, val, j);
    else
      upd(2 * node + 1, mid + 1, end, idx, val, j);
    tr[j][node] = tr[j][2 * node] + tr[j][2 * node + 1];
  }
}
long long qry(long long node, long long start, long long end, long long qstart,
              long long qend, long long j) {
  if (qstart > end || qend < start) {
    return 0;
  } else if (start >= qstart && qend >= end) {
    return tr[j][node];
  }
  long long mid = (start + end) / 2;
  return qry(2 * node, start, mid, qstart, qend, j) +
         qry(2 * node + 1, mid + 1, end, qstart, qend, j);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long n, k;
  cin >> n >> k;
  dp[0][0] = 1;
  for (int i = 1; i < 100005; i++) {
    dp[i][0] = 1;
    for (int j = 1; j < min(11, i + 1); j++) {
      dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
    }
  }
  long long ans = 0, x;
  for (int i = 0; i < n; i++) {
    cin >> x;
    upd(1, 1, 100005 - 1, x, 1, 1);
    for (int j = 2; j < k + 2; j++) {
      long long tmp = qry(1, 1, 100005 - 1, 1, x - 1, j - 1);
      upd(1, 1, 100005 - 1, x, tmp, j);
    }
  }
  cout << tr[k + 1][1] << endl;
  return 0;
}
long long choose(long long n, long long k) {
  if (k == 0) return 1;
  return (n * choose(n - 1, k - 1)) / k;
}
bool isprime(long long n) {
  for (long long i = 2; i * i <= n; i++) {
    if (n % i == 0) return false;
  }
  return true;
}
long long power(long long x, long long y, long long p) {
  long long res = 1;
  x = x % p;
  while (y > 0) {
    if (y & 1) res = (res * x) % p;
    y = y >> 1;
    x = (x * x) % p;
  }
  return res;
}
long long power(long long x, long long y) {
  long long res = 1;
  while (y > 0) {
    if (y & 1) res = res * x;
    y = y >> 1;
    x = x * x;
  }
  return res;
}

### 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>
using namespace std;
long long choose(long long n, long long k);
bool isprime(long long n);
long long power(long long x, long long y, long long p);
long long power(long long x, long long y);
long long tr[12][4 * 100005];
long long dp[100005][12] = {};
void upd(long long node, long long start, long long end, long long idx,
         long long val, long long j) {
  if (start == end) {
    tr[j][node] += val;
  } else {
    long long mid = (start + end) / 2;
    if (idx >= start && idx <= mid)
      upd(2 * node, start, mid, idx, val, j);
    else
      upd(2 * node + 1, mid + 1, end, idx, val, j);
    tr[j][node] = tr[j][2 * node] + tr[j][2 * node + 1];
  }
}
long long qry(long long node, long long start, long long end, long long qstart,
              long long qend, long long j) {
  if (qstart > end || qend < start) {
    return 0;
  } else if (start >= qstart && qend >= end) {
    return tr[j][node];
  }
  long long mid = (start + end) / 2;
  return qry(2 * node, start, mid, qstart, qend, j) +
         qry(2 * node + 1, mid + 1, end, qstart, qend, j);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long n, k;
  cin >> n >> k;
  dp[0][0] = 1;
  for (int i = 1; i < 100005; i++) {
    dp[i][0] = 1;
    for (int j = 1; j < min(11, i + 1); j++) {
      dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
    }
  }
  long long ans = 0, x;
  for (int i = 0; i < n; i++) {
    cin >> x;
    upd(1, 1, 100005 - 1, x, 1, 1);
    for (int j = 2; j < k + 2; j++) {
      long long tmp = qry(1, 1, 100005 - 1, 1, x - 1, j - 1);
      upd(1, 1, 100005 - 1, x, tmp, j);
    }
  }
  cout << tr[k + 1][1] << endl;
  return 0;
}
long long choose(long long n, long long k) {
  if (k == 0) return 1;
  return (n * choose(n - 1, k - 1)) / k;
}
bool isprime(long long n) {
  for (long long i = 2; i * i <= n; i++) {
    if (n % i == 0) return false;
  }
  return true;
}
long long power(long long x, long long y, long long p) {
  long long res = 1;
  x = x % p;
  while (y > 0) {
    if (y & 1) res = (res * x) % p;
    y = y >> 1;
    x = (x * x) % p;
  }
  return res;
}
long long power(long long x, long long y) {
  long long res = 1;
  while (y > 0) {
    if (y & 1) res = res * x;
    y = y >> 1;
    x = x * x;
  }
  return res;
}

```