{-# LANGUAGE BangPatterns      #-} --引数に!
{-# LANGUAGE MultiWayIf        #-}
{-# LANGUAGE TupleSections     #-}

import Data.List
import Data.Array.Unboxed
import Data.Array.MArray
import Data.Array.ST
import Data.Vector.Unboxed as V ((!),fromList,Vector)
import Control.Monad
import Control.Monad.ST
import Debug.Trace

type DP s = STUArray s (Int,Int) Int

dp_i :: DP s-> Int -> Int -> Int -> ST s ()
dp_i dparr ai i j = do
    now  <- readArray dparr (i,j)
    traceShow ((i,j),"now = ",now) $ return ()
    if now == -1 then return ()
      else forM_ [max 0 (j-ai)..j] $ \j0 -> do
        next <- readArray dparr (i+1,j0)
        writeArray dparr (i+1,j0) ((max 0 next)+now)

solve :: Int -> Int -> Vector Int -> ST s Int
solve n k as = do
  dparr <- newArray ((0,0),(n,k)) (-1)
  writeArray dparr (0,k) 1
  dp_i dparr (as V.! 0) 0 k
  forM_ [1..(n-1)] $ \i ->
    forM_ [0..k] $ \j -> dp_i dparr (as V.! i) i j
  readArray dparr (n,0)

main :: IO ()
main = do
  [n,k]  <- map read.words <$> getLine
  as <- map read.words <$> getLine
  putStrLn $ show $ max 0 $ runST $ solve n k (V.fromList as)

-------------------------
mod0 :: Int -> Int
mod0 n = mod n 1000000007
