N, K = map(int, raw_input().split())
a = map(int, raw_input().split())

dp = [[0]*(K+1) for _ in xrange(N+1)]
dp[0][0] = 1

for i in xrange(N):
    for j in xrange(K+1):
        for k in xrange(a[i]+1):
            if j-k>=0:
                dp[i+1][j] += dp[i][j-k]

print dp
print dp[-1][-1] % 1000000009