複数の配列から先頭1つずつを取り，取ったものをsortして$M$の末尾に加える．最終的に$V$と一致する通りを求める．
$$ dp[pos][n] := 前回n個取り，pos目まで見た時の組み合わせ $$
取る数は必ず広義単調減少となり増えることはない．前回$n$個取った場合に今回$r (0 \leq r \leq n)$個取るとすると，まず$n$個の場所に$r$個を当てはめるために$_{n}C_{r}$通り，また$r$個はどんな順番でも良いので$r$の並び方$r!$通りある．現在$pos$まで見て，$r$個取ったとすると次の遷移は$(pos + r, r)$である．$r$個取る時は，$V$の$[pos, pos + r)$が単調増加になっていなければならないことに注意する．
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define REP(i,k,n) for(int i=k;i<(int)(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair
#define fi first
#define se second
#define MOD 1000000007
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
ll dp[1205][1205], up[1205][1205], fact[1205];
ll C[2005][2005];
void combination(int size) {
for (int i = 0; i < size; i++) C[i][0] = 1LL;
for (int i = 1; i < size; i++) {
for (int j = 1; j <= i; j++) {
C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
}
}
}
int n;
ll dfs(int pos, int len) {
if(len == -1) {
ll res = 0;
for(ll i = 1; i <= n && pos + i <= n; i++) {
if(up[pos][pos + i - 1]) {
res += dfs(pos + i, i) % MOD;
res %= MOD;
} else break;
}
return dp[pos][len] = res;
} else {
if(dp[pos][len] != -1) return dp[pos][len];
if(pos == n) return 1;
ll res = 0;
for(ll i = 1; i <= len && pos + i <= n; i++) {
if(up[pos][pos + i - 1]) {
res += (((C[len][len-i] * fact[i]) % MOD) * dfs(pos + i, i)) % MOD;
res %= MOD;
} else break;
}
return dp[pos][len] = res;
}
}
int main() {
cin >> n;
vector<int> v(n);
rep(i, n) cin >> v[i];
combination(1205);
fact[0] = 1;
REP(i, 1, 1205) {
fact[i] = (i * fact[i-1]) % MOD;
}
rep(i, n + 1) {
rep(j, n + 1) {
dp[i][j] = -1;
up[i][j] = false;
}
}
rep(i, n) {
bool flag = true;
REP(j, i, n) {
up[i][j] = flag;
if(j < n-1 && v[j] > v[j+1]) flag = false;
}
}
cout << dfs(0, -1) << endl;
return 0;
}
本番中に解けなかった．悔しい．