#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 10;
typedef long long ll;
//ll par[2000010],sizem[2000010],sizel[2000010],size[2000010],a,b,q1,q2,q3,x,y;
ll a[101];
ll dp[101][100001];
ll sum[100001];
ll solve(ll i,ll j,ll player=1)
{
	if(i>j)
		return 0;
	if(i>n)
		return 0;
	if(j<1)
		return 0;
	ll maxi = -1;
	ll max2 = -1;
	if(dp[i][j][player]!=-1)
		return dp[i][j][player];
	ll &ans = dp[i][j][player];
	if(player==1)
		ans=max(a[i]+solve(i+1,j,2),a[j]+solve(i,j-1,2));
	if(player==2)
		ans=min(-a[j]+solve(i,j-1,1),-a[i]+solve(i+1,j,1));
	return ans;
}
ll calc(ll a,ll b)
{
	if(b<=0)
		return sum[a];
	return (sum[a]-sum[b-1]+mod)%mod;
}

int main()
{
	cin>>n>>k;
	dp[0][0];
	for (int i = 1; i <= n; ++i)
	{
		dp[i][0]=1;
		cin>>a[i];
	}
	memset(dp,-1,sizeof(dp));
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j <= ; ++j)
		{
			sum[0]=dp[i-1][0];
			for (int j = 1; j < k; ++j)
			{
				sum[j]=(sum[j-1]+dp[i-1][j])%mod;
			}
			for (int i = 1; i <= k; ++i)
			{
				dp[i][j]=calc(j,j-a[i]);
			}
		}
	}
	cout<<dp[n][k]<<endl;
	return 0;
}