{-# LANGUAGE BangPatterns #-} import Control.Monad import Control.Monad.ST import Control.Monad.State.Strict import Data.Char import qualified Data.ByteString.Char8 as BSC8 import qualified Data.Vector.Fusion.Stream.Monadic as VFSM import qualified Data.Vector.Unboxed as VU import qualified Data.Vector.Unboxed.Mutable as VUM stream :: Monad m => Int -> Int -> VFSM.Stream m Int stream !l !r = VFSM.Stream step l where step x | x < r = return $ VFSM.Yield x (x + 1) | otherwise = return $ VFSM.Done {-# INLINE [0] step #-} {-# INLINE [1] stream #-} rep :: Monad m => Int -> (Int -> m ()) -> m () rep n = flip VFSM.mapM_ (stream 0 (n + 1)) {-# INLINE rep #-} rep' :: Monad m => Int -> (Int -> m ()) -> m () rep' n = flip VFSM.mapM_ (stream 0 n) {-# INLINE rep' #-} rep1 :: Monad m => Int -> (Int -> m ()) -> m () rep1 n = flip VFSM.mapM_ (stream 1 (n + 1)) {-# INLINE rep1 #-} rep1' :: Monad m => Int -> (Int -> m ()) -> m () rep1' n = flip VFSM.mapM_ (stream 1 (n + 1)) {-# INLINE rep1' #-} main :: IO () main = do n <- readLn :: IO Int dp <- VUM.replicate 100100 (1 :: Int) VUM.unsafeWrite dp 0 (0 :: Int) rep1 9 $ \i -> rep 100000 $ \j -> do when (i + j <= 100000) $ do item1 <- VUM.unsafeRead dp (j + i) item2 <- VUM.unsafeRead dp j VUM.unsafeWrite dp (j + i) (mod (item1 + item2) 1000000009) rep' n $ \_ -> do m <- readLn :: IO Int print =<< VUM.unsafeRead dp (m `div` 111111)