记录编号	607131	评测结果	AAAAAAAAAA
题目名称	4180.毛二琛	最终得分	100
用户昵称	梦那边的美好TT	是否通过	通过
代码语言	C++	运行时间	0.789 s
提交时间	2025-10-05 17:29:50	内存使用	72.71 MiB

#include <bits/stdc++.h>
#define ll long long
#define N 5001
using namespace std;
const int MOD=1e9+7;
int n,a[N];
bool c[N];
ll dp[N][N],g[N][N],ans;
int main(){
    freopen("swap.in","r",stdin);
    freopen("swap.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n;
    for(int i=0;i<n;++i) cin>>a[i];
    for(int i=0;i<n;++i){
        if(i<a[i]){
            c[i-1]=true;
            c[a[i]-1]=true;
        }else for(int j=a[i];j<i-1;++j) c[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(c[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;
    cout<<ans<<'\n';
    return 0;
}