simple 4 死活过不去。

#include<bits/stdc++.h>
#define mod 1000000009 
using namespace std;
long long n,K,a[5200010],f[5200010]={1},sum[5200010];
int main(){
	cin>>n>>K;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++){
		sum[0]=1;
		for(int j=1;j<=K;j++){
			sum[j]=sum[j-1]+f[j];
			sum[j]%=mod;
		}
		for(long long j=1;j<=K;j++){
			f[j]=sum[j]-(j>a[i]?sum[j-a[i]-1]:0ll)+mod;
			f[j]%=mod;
		}
	}
	cout<<f[K];
}