记录编号	607108	评测结果	AAAAAAAAAA
题目名称	4180.毛二琛	最终得分	100
用户昵称	对立猫猫对立	是否通过	通过
代码语言	C++	运行时间	0.753 s
提交时间	2025-10-05 16:54:04	内存使用	72.84 MiB

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
int n;
int a[5001];
bool com[5001];
long long dp[5001][5001], g[5001][5001];
long long ans;
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%d", &a[i]);
	for (int i = 0; i < n; i++)
		if (i < a[i]) {
			com[i - 1] = 1;
			com[a[i] - 1] = 1;
		} else for (int j = a[i]; j < i - 1; j++) com[j] = 1;
	dp[0][1] = g[0][1] = 1;
	for (int i = 1; i < n - 1; i++)
		for (int j = 1; j <= i + 1; j++) {
			if (com[i - 1]) dp[i][j] = (dp[i][j] + g[i - 1][i] - g[i - 1][j - 1] + MOD) % MOD;
			else dp[i][j] = (dp[i][j] + g[i - 1][j - 1]) % MOD;
			g[i][j] = (g[i][j - 1] + dp[i][j]) % MOD;
		}
	for (int i = 1; i < n; i++) ans = (ans + dp[n - 2][i]) % MOD;
	printf("%lld", ans);
	return 0;
}