#include #define int long long #define all(v) v.begin(),v.end() #define rall(v) v.rbegin(),v.rend() using namespace std; templateistream&operator>>(istream&I,vector&v){for(auto&i:v)I>>i;return I;} templateostream&operator<<(ostream&O,vector&v){for(auto&i:v)O<>n; vector>dp(n+1,vector(n+1)),DP(n+1,vector(n+1)); dp[0][0]=1; DP[1][1]=1; vectora(n); for(int i=2;is=dp[i-1],t=DP[i-1]; for(int j=1;j<=n;j++){ (s[j]+=s[j-1])%=mod; (t[j]+=t[j-1])%=mod; } for(int j=1;j<=n;j++){ dp[i][j]=s[min(n,j+a[i-1])]; if(i!=1)DP[i][j]=t[min(n,j+a[i-1])]; } } int sum=0; for(int i=1;i<=n;i++)(sum+=dp[n][i])%=mod; cout<<(sum-DP[n][n]+mod)%mod<>t; while(t--)AC::solve(); }