记录编号	607097	评测结果	AAAAAAAAAA
题目名称	4180.毛二琛	最终得分	100
用户昵称	xuyuqing	是否通过	通过
代码语言	C++	运行时间	0.845 s
提交时间	2025-10-05 15:51:10	内存使用	72.52 MiB

#include <iostream>

using namespace std;

const int N = 5114;
const long long MOD = 1e9 + 7;

int n;
int nums[N];
bool flag[N];
long long dp[N][N];
long long g[N][N];
long long res;

int main () {
	
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> nums[i];
		if (i < nums[i]) {
			flag[i - 1] = flag[nums[i] - 1] = true;
		}
		else {
			for (int j = nums[i]; j < i - 1; j++) {
				flag[j] = true;
			}
		}
	}

	dp[0][1] = g[0][1] = 1;
	for (int i = 1; i < n - 1; i++) {
		for (int j = 1; j <= i + 1; j++) {
			if (flag[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++) {
		res = (res + dp[n - 2][i]) % MOD;
	}

	cout << res << endl;
	
	return 0;
}