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

import Data.Maybe (fromJust)
import Data.List
import Data.Array  --変数衝突
import Data.Array.Unboxed
import Data.Array.MArray
import Data.Array.ST
--import Data.Vector as V　--変数衝突
import qualified Data.ByteString.Lazy.Char8 as B
import qualified Data.Vector.Unboxed as V
import Control.Monad
import Control.Monad.ST
--import Debug.Trace

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

--O(10*D)
dp_i :: DP s -> [Int] -> Int -> Int -> ST s ()
dp_i dparr ks d cnt = sub dparr ks cnt
 where
   sub :: DP s -> [Int] -> Int -> ST s ()
   sub dparr [] _ = return ()
   sub dparr (k:ks) cnt = do
     let modd n = if n < d then n else mod n d
     forM_ [0..d-1] $ \i -> do
       forM_ [0..k-1] $ \j -> do
         a1 <- readArray dparr (cnt,i,False)
         a2 <- readArray dparr (cnt,i,True)
         c <- readArray dparr (cnt+1,modd $ i+j,False)
         writeArray dparr (cnt+1,modd $ i+j,False) (mod' $ a1+a2+c)
       forM_ [False,True] $ \bool -> do -- j == k
         a <- readArray dparr (cnt,i,bool)
         c <- readArray dparr (cnt+1,modd $ i+k,bool)
         writeArray dparr (cnt+1,modd $ i+k,bool) (mod' a+c)
       forM_ [k+1..9] $ \j -> do
         a <- readArray dparr (cnt,i,False)
         c <- readArray dparr (cnt+1,modd $ i+j,False)
         writeArray dparr (cnt+1,modd $ i+j,False) (mod' a+c)
     sub dparr ks (cnt+1)

solve :: [Int] -> Int -> ST s Int -- length ks == n
solve ks d = do
  dparr <- newArray ((0,0,False),(length ks,d-1,True)) 0
  writeArray dparr (0,0,True) 1
  dp_i dparr ks d 0
  ans <- forM [False,True] $ \bool -> readArray dparr (length ks,0,bool)
  return $ mod' $ (sum ans) - 1 -- K >= 1　より全部ゼロを除く

main0 :: B.ByteString -> Int
main0 cont =
   let remLines0 = map B.words (B.lines cont)
       [k']:remLines1 = remLines0
       ks = map readBInt $ B.groupBy (\_ _ -> False) k'
       [d']:remLines2 = remLines1
       d = readBInt d'
   in runST $ solve ks d

readBInt :: B.ByteString -> Int
readBInt = fst . fromJust . B.readInt

main :: IO ()
main = print . main0 =<< B.getContents

mod' :: Int -> Int
mod' n = if n < 1000000007 then n else mod n 1000000007
