{-# LANGUAGE BangPatterns #-} {-# LANGUAGE BinaryLiterals #-} {-# LANGUAGE CPP #-} {-# LANGUAGE DeriveFunctor #-} {-# LANGUAGE DerivingStrategies #-} {-# LANGUAGE DerivingVia #-} {-# LANGUAGE FlexibleContexts #-} {-# LANGUAGE FlexibleInstances #-} {-# LANGUAGE GeneralizedNewtypeDeriving #-} {-# LANGUAGE KindSignatures #-} {-# LANGUAGE LambdaCase #-} {-# LANGUAGE MagicHash #-} {-# LANGUAGE MultiParamTypeClasses #-} {-# LANGUAGE MultiWayIf #-} {-# LANGUAGE NumericUnderscores #-} {-# LANGUAGE OverloadedStrings #-} {-# LANGUAGE PatternSynonyms #-} {-# LANGUAGE RankNTypes #-} {-# LANGUAGE RecordWildCards #-} {-# LANGUAGE ScopedTypeVariables #-} {-# LANGUAGE StandaloneDeriving #-} {-# LANGUAGE TupleSections #-} {-# LANGUAGE TypeApplications #-} {-# LANGUAGE TypeFamilies #-} {-# LANGUAGE TypeInType #-} {-# LANGUAGE UnboxedTuples #-} ------------------------------------------------------------------------------- ------------------------------------------------------------------------------- ------------------------------------------------------------------------------- {- base -} import Control.Applicative import qualified Control.Arrow as Arrow import Control.Monad import Control.Monad.ST import Data.Bits import Data.Bool import qualified Data.Char as Char import Data.Complex import qualified Data.Foldable as Foldable import Data.Function import Data.Ix import qualified Data.List as List import Data.Maybe import Data.Monoid import Data.Ord import Data.Ratio import Data.Semigroup import qualified Data.Word as Word import Foreign hiding (void) import GHC.Exts import Unsafe.Coerce {- array -} import qualified Data.Array.IO as ArrIO import qualified Data.Array.MArray as ArrMA import qualified Data.Array.ST as ArrST import qualified Data.Array.Storable as ArrStore import qualified Data.Array.Unboxed as ArrU {- bytestring -} import qualified Data.ByteString as BS import qualified Data.ByteString.Builder as BSB import qualified Data.ByteString.Builder.Extra as BSBE import qualified Data.ByteString.Char8 as BSC8 import qualified Data.ByteString.Lazy as BSL import qualified Data.ByteString.Lazy.Builder as BSLB import qualified Data.ByteString.Lazy.Char8 as BSLC8 import qualified Data.ByteString.Unsafe as BSU {- containers -} import qualified Data.Graph as Graph import Data.IntMap (IntMap) import qualified Data.IntMap as IntMap import Data.IntSet (IntSet) import qualified Data.IntSet as IntSet import qualified Data.Sequence as Seq import qualified Data.Tree as Tree {- integer-gmp -} import GHC.Integer.GMP.Internals {- time -} import qualified Data.Time.Calendar as Calender import qualified Data.Time.Calendar.Easter as CalenderE import qualified Data.Time.Calendar.Julian as CalenderJ import qualified Data.Time.Calendar.MonthDay as CalenderM import qualified Data.Time.Calendar.OrdinalDate as CalenderD import qualified Data.Time.Calendar.WeekDate as CalenderW import qualified Data.Time.LocalTime as LocalTime {- transformers -} import qualified Control.Monad.Trans.Accum as TAccum import qualified Control.Monad.Trans.Cont as TCont import qualified Control.Monad.Trans.Identity as TId import qualified Control.Monad.Trans.Reader as TReader import qualified Control.Monad.Trans.State.Lazy as TStateL import qualified Control.Monad.Trans.State.Strict as TStateS import qualified Control.Monad.Trans.Writer.CPS as TWriteC import qualified Control.Monad.Trans.Writer.Lazy as TWriteL import qualified Control.Monad.Trans.Writer.Strict as TWriteS {- vector -} import qualified Data.Vector as V import qualified Data.Vector.Generic as VG import qualified Data.Vector.Generic.Mutable as VGM import qualified Data.Vector.Mutable as VM import qualified Data.Vector.Primitive as VP import qualified Data.Vector.Primitive.Mutable as VPM import qualified Data.Vector.Unboxed as VU import qualified Data.Vector.Unboxed.Mutable as VUM ------------------------------------------------------------------------------- ------------------------------------------------------------------------------- ------------------------------------------------------------------------------- main :: IO () main = do (n, m) <- parse2 print $ bool 1 (solve n m) (n <= m && n /= 1) solve :: Int -> Int -> Int solve n m = List.foldl1' (+%) $ map g [0..(m `div` n)] where g :: Int -> Int g i = let rest = m - (i * n) in nCk (rest + i) i ------------------------------------------------------------------------------- modulus :: Int modulus = 998244353 infixr 8 ^% infixl 7 *%, /% infixl 6 +%, -% (+%) :: Int -> Int -> Int (+%) x y | x + y >= modulus = x + y - modulus | otherwise = x + y {-# INLINE (+%) #-} (-%) :: Int -> Int -> Int (-%) x y | x - y < 0 = (x - y) + modulus | otherwise = x - y {-# INLINE (-%) #-} (*%) :: Int -> Int -> Int (*%) x y = (x * y) `mod` modulus {-# INLINE (*%) #-} (/%) :: Int -> Int -> Int (/%) x y = go y modulus 1 0 where go a b u v | b > 0 = case a `quot` b of q -> go b (a - (q * b)) v (u - (q * v)) | otherwise = (x * (u + modulus)) `rem` modulus {-# INLINE (/%) #-} (^%) :: Int -> Int -> Int (^%) x n | n > 0 = go 1 x n | n == 0 = 1 | otherwise = go 1 ((/%) 1 x) (-n) where go !acc !y !m | m .&. 1 == 0 = go acc (y *% y) (unsafeShiftR m 1) | m == 1 = acc *% y | otherwise = go (acc *% y) (y *% y) (unsafeShiftR (m - 1) 1) {-# INLINE (^%) #-} gcdExt :: Int -> Int -> (Int, Int, Int) gcdExt a 0 = (1, 0, a) gcdExt a b = let (q, r) = a `quotRem` b (s, t, g) = gcdExt b r in (t, s - q * t, g) {-# INLINE gcdExt #-} modInv :: Int -> Int -> Int modInv a mo | 1 == g = mkPos i | otherwise = -1 where (i, _, g) = gcdExt a mo mkPos x | x < 0 = x + mo | otherwise = x fact :: Int -> Int fact = VU.unsafeIndex factCache {-# INLINE fact #-} recipFact :: Int -> Int recipFact = VU.unsafeIndex recipFactCache {-# INLINE recipFact #-} invFact :: Int -> Int invFact x = recipFact x *% fact (x - 1) {-# INLINE invFact #-} nPk :: Int -> Int -> Int nPk n k | n < k = 0 | otherwise = fact n *% recipFact k {-# INLINE nPk #-} nCk :: Int -> Int -> Int nCk n k | n < k = 0 | otherwise = fact n *% recipFact (n - k) *% recipFact k {-# INLINE nCk #-} nHk :: Int -> Int -> Int nHk n k | n < 0 || k < 0 = 0 | k == 0 = 1 | otherwise = nCk (n + k - 1) k {-# INLINE nHk #-} factCache :: VU.Vector Int factCache = VU.scanl' (*%) 1 $ VU.generate 1000000 (+1) {-# NOINLINE factCache #-} recipFactCache :: VU.Vector Int recipFactCache = VU.scanr' (*%) (1 /% factCache VU.! 1000000) $ VU.generate 1000000 (+ 1) {-# NOINLINE recipFactCache #-} ------------------------------------------------------------------------------- ------------------------------------------------------------------------------- type Parser a = BSC8.ByteString -> Maybe (a, BSC8.ByteString) parseInt :: Parser Int parseInt = fmap (Arrow.second BSC8.tail) . BSC8.readInt parseChar :: [Char] -> VU.Vector Char parseChar = VU.fromList parse1 :: IO Int parse1 = readLn parse2 :: IO (Int, Int) parse2 = (\vec -> (vec VU.! 0, vec VU.! 1)) . VU.unfoldrN 2 parseInt <$> BSC8.getLine parse3 :: IO (Int, Int, Int) parse3 = (\vec -> (vec VU.! 0, vec VU.! 1, vec VU.! 2)) . VU.unfoldrN 3 parseInt <$> BSC8.getLine parse4 :: IO (Int, Int, Int, Int) parse4 = (\vec -> (vec VU.! 0, vec VU.! 1, vec VU.! 2, vec VU.! 3)) . VU.unfoldrN 4 parseInt <$> BSC8.getLine parseM :: Int -> IO (VU.Vector Int) parseM m = VU.unfoldrN m parseInt <$> BSC8.getLine parseN :: Int -> IO (VU.Vector Int) parseN n = VU.replicateM n parse1 parseNM :: Int -> Int -> IO (V.Vector (VU.Vector Int)) parseNM n m = V.replicateM n $ VU.unfoldrN m parseInt <$> BSC8.getLine parseANBN :: Int -> IO (VU.Vector Int, VU.Vector Int) parseANBN n = do vectup <- VU.replicateM n $ (\vec -> (vec VU.! 0, vec VU.! 1)) . VU.unfoldr (BSC8.readInt . BSC8.dropWhile Char.isSpace) <$> BSC8.getLine return $ VU.unzip vectup parseANBNCN :: Int -> IO (VU.Vector Int, VU.Vector Int, VU.Vector Int) parseANBNCN n = do vectup <- VU.replicateM n $ (\vec -> (vec VU.! 0, vec VU.! 1, vec VU.! 2)) . VU.unfoldr (BSC8.readInt . BSC8.dropWhile Char.isSpace) <$> BSC8.getLine return $ VU.unzip3 vectup ------------------------------------------------------------------------------- ------------------------------------------------------------------------------- -------------------------------------------------------------------------------