#include<bits/stdc++.h>
using namespace std;
int p=1e+9;
int candies(int n,int k,int a[],int j,long long memo[][105]){
	long long ans=0;
	if(j==n){
		if(k==0)
			return 1;
		else 
			return 0;
	}
	if(memo[k][j]==-1){
	for(int i=0;i<=a[j];i++){
		ans=(ans%p+candies(n,k-i,a,j+1,memo)%p)%p;
	}
	}
	else
		return memo[k][j];

	memo[k][j]=ans%p;
	return ans%p;
}
int main(){
	int n,k;
	cin>>n>>k;

	int a[n+5];
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
  
    long long memo[k+1][105];
	memset(memo,-1,sizeof(memo));
	long long ans=candies(n,k,a,0);
	/*for(int i=0;i<=k;i++){
		for(int j=0;j<=n;j++){
			cout<<memo[i][j]<<" ";
		}
		cout<<endl;
	}*/
	cout<<ans<<endl;
	return 0;
}
