Problem: Reordering the Documents

Susan is good at arranging her dining table for convenience, but not her office desk.

Susan has just finished the paperwork on a set of documents, which are still piled on her desk. They have serial numbers and were stacked in order when her boss brought them in. The ordering, however, is not perfect now, as she has been too lazy to put the documents slid out of the pile back to their proper positions. Hearing that she has finished, the boss wants her to return the documents immediately in the document box he is sending her. The documents should be stowed in the box, of course, in the order of their serial numbers.

The desk has room just enough for two more document piles where Susan plans to make two temporary piles. All the documents in the current pile are to be moved one by one from the top to either of the two temporary piles. As making these piles too tall in haste would make them tumble, not too many documents should be placed on them. After moving all the documents to the temporary piles and receiving the document box, documents in the two piles will be moved from their tops, one by one, into the box. Documents should be in reverse order of their serial numbers in the two piles to allow moving them to the box in order.

For example, assume that the pile has six documents #1, #3, #4, #2, #6, and #5, in this order from the top, and that the temporary piles can have no more than three documents. Then, she can form two temporary piles, one with documents #6, #4, and #3, from the top, and the other with #5, #2, and #1 (Figure E.1). Both of the temporary piles are reversely ordered. Then, comparing the serial numbers of documents on top of the two temporary piles, one with the larger number (#6, in this case) is to be removed and stowed into the document box first. Repeating this, all the documents will be perfectly ordered in the document box.

<image>
Figure E.1. Making two temporary piles

Susan is wondering whether the plan is actually feasible with the documents in the current pile and, if so, how many different ways of stacking them to two temporary piles would do. You are asked to help Susan by writing a program to compute the number of different ways, which should be zero if the plan is not feasible.

As each of the documents in the pile can be moved to either of the two temporary piles, for $n$ documents, there are $2^n$ different choice combinations in total, but some of them may disturb the reverse order of the temporary piles and are thus inappropriate.

The example described above corresponds to the first case of the sample input. In this case, the last two documents, #5 and #6, can be swapped their destinations. Also, exchanging the roles of two temporary piles totally will be OK. As any other move sequences would make one of the piles higher than three and/or make them out of order, the total number of different ways of stacking documents to temporary piles in this example is $2 \times 2 = 4$.

Input

The input consists of a single test case of the following format.


$n$ $m$
$s_1$ ...  $s_n$


Here, $n$ is the number of documents in the pile ($1 \leq n \leq 5000$), and $m$ is the number of documents that can be stacked in one temporary pile without committing risks of making it tumble down ($n/2 \leq m \leq n$). Numbers $s_1$ through $s_n$ are the serial numbers of the documents in the document pile, from its top to its bottom. It is guaranteed that all the numbers $1$ through $n$ appear exactly once.

Output

Output a single integer in a line which is the number of ways to form two temporary piles suited for the objective. When no choice will do, the number of ways is $0$, of course.

If the number of possible ways is greater than or equal to $10^9 + 7$, output the number of ways modulo $10^9 + 7$.

Sample Input 1


6 3
1 3 4 2 6 5


Sample Output 1


4


Sample Input 2


6 6
1 3 4 2 6 5


Sample Output 2


8


Sample Input 3


4 4
4 3 1 2


Sample Output 3


0






Example

Input

6 3
1 3 4 2 6 5


Output

4

Solution (in CPP):

Solution:
// vvvvvvvvvvvv TEMPLATE vvvvvvvvvvvv
#include <bits/stdc++.h>
using namespace std; using ll = long long; using P = pair<ll, ll>;
const ll linf = 1e18; const double eps = 1e-12, pi = acos(-1);
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define each(i,a) for (auto&& i : a)
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
#define pb push_back
#define eb emplace_back
#define all(a) begin(a),end(a)
#define chmin(x,v) x = min(x, v)
#define chmax(x,v) x = max(x, v)
#define min(x,y) (x < y ? x : y)
#define max(x,y) (x < y ? y : x)
template<typename Head> void out(Head h) { cout << h << endl; } template<typename Head, typename... Tail>void out(Head h, Tail... t) { cout << h << " "; out(t...); }
template<typename T> istream& operator>>(istream& is, vector<T>& v) { each(x,v) is >> x; return is; }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) { rep(i,v.size()) { if (i) os << " "; os << v[i]; } return os; }
template<typename T> ostream& operator<<(ostream& os, const vector<string>& v) { rep(i,v.size()) { if (i) os << endl; os << v[i]; } return os; }
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v) { rep(i,v.size()) { if (i) os << endl; os << v[i]; } return os; }
struct yes_no : std::numpunct<char> { string_type do_truename() const { return "Yes"; } string_type do_falsename() const { return "No"; } };
void solve(); int main() {
  ios::sync_with_stdio(false); cin.tie(0); locale loc(locale(), new yes_no); cout.imbue(loc); cout << fixed << setprecision(10) << boolalpha;
  solve();
}
// ^^^^^^^^^^^^ TEMPLATE ^^^^^^^^^^^^

template <class Monoid>
class SegmentTree {
  using T = typename Monoid::type;
  const int size_, n;
  std::vector<T> data;
  int expand(int m) const { return m <= 1 ? 1 : expand((m + 1) / 2) * 2; }
public:
  SegmentTree() : SegmentTree(0) {}
  SegmentTree(const std::vector<T> &vec) :
    size_(vec.size()), n(expand(size_)), data(n * 2, Monoid::id()) {
    std::copy(begin(vec), end(vec), begin(data) + n);
    for (int i = n - 1; i >= 0; --i) {
      data[i] = Monoid::op(data[i * 2 + 0], data[i * 2 + 1]);
    }
  }
  SegmentTree(const int count, const T &value = Monoid::id()) :
    SegmentTree(std::vector<T>(count, value)) {}
  int size() const { return size_; }
  void update(int pos, const T &value) {
    assert (0 <= pos && pos < size_); // assertion
    data[pos += n] = value;
    while (pos /= 2) {
      data[pos] = Monoid::op(data[pos * 2], data[pos * 2 + 1]);
    }
  }
  T find(int l, int r) const {
    assert (0 <= l && l <= r && r <= size_); // assertion
    l += n; r += n;
    T res1 = Monoid::id(), res2 = Monoid::id();
    while (l != r) {
      if (l % 2) res1 = Monoid::op(res1, data[l++]);
      if (r % 2) res2 = Monoid::op(data[--r], res2);
      l /= 2; r /= 2;
    }
    return Monoid::op(res1, res2);
  }
  T operator[](size_t pos) {
    return data[n+pos];
  }
  using value_type = T;
  using update_type = T;
};

struct Min {
  using type = ll;
  static type id() { return linf; }
  static type op(const type &l, const type &r) { return min(l, r); }
};
struct Max {
  using type = ll;
  static type id() { return -linf; }
  static type op(const type &l, const type &r) { return max(l, r); }
};
struct Sum {
  using type = ll;
  static type id() { return 0; }
  static type op(const type &l, const type &r) { return l + r; }
};

struct Node {
  ll n1, n2;
};

Node f(const vector<ll>& a, ll l, ll r) {
  ll cnt = 0, prv = -linf, prv2 = -linf;
  rep(i, l, r) {
    if (a[i] > prv) {
      prv = a[i];
      ++cnt;
    }
    else if (a[i] > prv2) {
      prv2 = a[i];
    }
    else {
      return {-1, -1};
    }
  }
  return {cnt, r-l-cnt};
}

constexpr ll mod = 1e9+7;
constexpr ll mul(ll a, ll b) { return a * b % mod; }
ll mul(initializer_list<ll> t) { ll res = 1; each(v, t) res = mul(res, v); return res; }
ll add(ll a, ll b) { return (a + b) % mod; }
ll add(initializer_list<ll> t) { ll res = 0; each(v, t) res = add(res, v); return res; }
ll sub(ll a, ll b) { return (a - b + mod) % mod; }
ll sub(initializer_list<ll> t) { auto it = t.begin(); ll res = *(it++); while (it != t.end()) res = sub(res, *(it++)); return res; }
ll inv(ll n); ll power(ll x, ll n) { if (n < 0) return inv(power(x, -n)); ll res = 1; for (ll i = 1; i <= n; i <<= 1) { if (i & n) res = mul(res, x); x = mul(x, x); } return res; }
ll inv(ll n) { return power(n, mod-2); }
ll divi(ll a, ll b) { return mul(a, inv(b)); }
ll divi(initializer_list<ll> t) { auto it = t.begin(); ll res = *(it++); while (it != t.end()) res = divi(res, *(it++)); return res; }
vector<ll> fact, rfact;
void init_fact(ll n) { fact.resize(n+1); fact[0] = 1; rep(i, n) fact[i+1] = mul(fact[i], i+1); rfact.resize(n+1); rfact[n] = inv(fact[n]); rrep(i, n) rfact[i] = mul(rfact[i], i+1); }
ll comb(ll n, ll r) { if (r < 0) return 0; if (r > n) return 0; return divi(fact[n], mul(fact[r], fact[n-r])); }
ll perm(ll n, ll r) { if (r < 0) return 0; if (r > n) return 0; return divi(fact[n], fact[n-r]); }

using Row = vector<ll>;
using Matrix = vector<Row>;
Matrix E(ll n) { Matrix res(n, Row(n, 0)); rep(i, n) res[i][i] = 1; return res; }
Matrix mul(const Matrix& A, const Matrix& B) { const ll n = A.size(), m = A[0].size(), l = B[0].size(); assert(m == B.size()); Matrix res(n, Row(l, 0)); rep(i, n) rep(j, m) rep(k, l) res[i][k] = add(res[i][k], mul(A[i][j], B[j][k])); return res; }
Row mul(const Matrix& A, const Row& x) { Matrix tx(x.size()); rep(i, x.size()) tx[i] = Row(1, x[i]); tx = mul(A, tx); Row res(x.size()); rep(i, x.size()) res[i] = tx[i][0]; return res; }
Matrix power(Matrix A, ll n) { assert(A.size() == A[0].size()); Matrix res = E(A.size()); for (ll i = 1; i <= n; i <<= 1) { if (i & n) res = mul(res, A); A = mul(A, A); } return res; }

void solve() {
  ll n, m; cin >> n >> m;
  vector<ll> a(n); cin >> a;
  each(x, a) --x;
  SegmentTree<Sum> seg(n);
  vector<Node> v;
  ll l = 0;
  rep(i, n) {
    seg.update(a[i], 1);
    if (seg.find(0, i+1) == i+1) {
      auto node = f(a, l, i+1);
      if (node.n1 < 0) {
        cout << 0 << endl;
        return;
      }
      v.pb(node);
      l = i+1;
    }
  }
  n = v.size();
  vector<vector<ll>> dp(n+1, vector<ll>(m+1, 0));
  dp[0][0] = 1;
  ll sum = 0;
  rep(i, n) {
    rep(j, m+1) {
      if (dp[i][j] == 0) continue;
      ll n1 = j, n2 = sum - j;
      assert(n2 >= 0);
      {
        ll nn1 = n1 + v[i].n1, nn2 = n2 + v[i].n2;
        if (nn1 <= m && nn2 <= m) {
          dp[i+1][nn1] = add(dp[i+1][nn1], dp[i][j]);
        }
      }
      {
        ll nn1 = n1 + v[i].n2, nn2 = n2 + v[i].n1;
        if (nn1 <= m && nn2 <= m) {
          dp[i+1][nn1] = add(dp[i+1][nn1], dp[i][j]);
        }
      }
    }
    sum += v[i].n1 + v[i].n2;
  }
  ll ans = 0;
  rep(j, m+1) {
    ans = add(ans, dp[n][j]);
  }
  cout << ans << endl;
}