{-# OPTIONS_GHC -O2 #-} {-# LANGUAGE BangPatterns, BinaryLiterals, CPP, DerivingStrategies #-} {-# LANGUAGE DerivingVia, FlexibleContexts, FlexibleInstances #-} {-# LANGUAGE GeneralizedNewtypeDeriving, KindSignatures, LambdaCase #-} {-# LANGUAGE MagicHash, MultiParamTypeClasses, MultiWayIf #-} {-# LANGUAGE NumericUnderscores, OverloadedStrings, PatternSynonyms #-} {-# LANGUAGE RankNTypes, RecordWildCards, ScopedTypeVariables #-} {-# LANGUAGE StandaloneDeriving, TupleSections, TypeApplications #-} {-# LANGUAGE TypeFamilies, TypeInType, UnboxedTuples, ViewPatterns #-} {- base -} import qualified Control.Arrow as Arrow import Control.Monad import Control.Monad.ST import qualified Data.Bits as Bits import qualified Data.Char as Char import qualified Data.Foldable as Foldable import qualified Data.List as List import Data.Monoid import Data.Ord import Data.Ratio import Data.Semigroup import qualified Data.Word as Word import GHC.Exts import Foreign hiding (void) import Unsafe.Coerce {- bytestring -} import qualified Data.ByteString.Char8 as BSC8 {- containers -} import Data.IntMap.Strict (IntMap) import qualified Data.IntMap.Strict as IntMap import Data.IntSet (IntSet) import qualified Data.IntSet as IntSet import qualified Data.Sequence as Seq {- mtl -} import Control.Monad.State.Strict {- transformers -} import Control.Monad.Reader {- 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 #define MOD 998244353 modulus :: (Num a) => a modulus = MOD {-# INLINE modulus #-} infixr 8 ^% infixl 7 *%, /% infixl 6 +%, -% (+%) :: Int -> Int -> Int (I# x#) +% (I# y#) = case x# +# y# of r# -> I# (r# -# ((r# >=# MOD#) *# MOD#)) {-# INLINE (+%) #-} (-%) :: Int -> Int -> Int (I# x#) -% (I# y#) = case x# -# y# of r# -> I# (r# +# ((r# <# 0#) *# MOD#)) {-# INLINE (-%) #-} (*%) :: Int -> Int -> Int (I# x#) *% (I# y#) = I# ((x# *# y#) `remInt#` MOD#) {-# INLINE (*%) #-} (/%) :: Int -> Int -> Int (I# x#) /% (I# y#) = go# y# MOD# 1# 0# where go# a# b# u# v# | isTrue# (b# ># 0#) = case a# `quotInt#` b# of q# -> go# b# (a# -# (q# *# b#)) v# (u# -# (q# *# v#)) | otherwise = I# ((x# *# (u# +# MOD#)) `remInt#` MOD#) {-# 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 Bits..&. 1 == 0 = go acc (y *% y) (Bits.unsafeShiftR m 1) | m == 1 = acc *% y | otherwise = go (acc *% y) (y *% y) (Bits.unsafeShiftR (m - 1) 1) newtype Mint = Mint{ getMint :: Int} deriving (Eq, Ord) -- Mintは数値 instance Num Mint where (+) = coerce (+%) (-) = coerce (-%) (*) = coerce (*%) abs = id signum = const (Mint 1) fromInteger x = Mint . fromInteger $ mod x modulus -- Mintは表示可能 instance Show Mint where show (Mint x) = show x -- Mintは上限・下限を持つ instance Bounded Mint where minBound = Mint 0 maxBound = Mint $ MOD - 1 -- Mintは列挙型 instance Enum Mint where toEnum = intMod fromEnum = fromIntegral -- Mintは実数 instance Real Mint where toRational (Mint x) = toRational x -- Mintは有理数 instance Fractional Mint where (Mint x) / (Mint y) = Mint (x /% y) fromRational q = fromInteger (numerator q) / fromInteger (denominator q) -- Mintは整数 instance Integral Mint where quotRem x y = (x / y, x - x / y * y) toInteger (Mint x) = toInteger x newtype instance VUM.MVector s Mint = MV_Mint (VUM.MVector s Int) newtype instance VU.Vector Mint = V_Mint (VU.Vector Int) -- MintをVectorに乗せることができる instance VU.Unbox Mint instance VGM.MVector VUM.MVector Mint where {-# INLINE basicLength #-} basicLength (MV_Mint v) = VGM.basicLength v {-# INLINE basicUnsafeSlice #-} basicUnsafeSlice i n (MV_Mint v) = MV_Mint $ VGM.basicUnsafeSlice i n v {-# INLINE basicOverlaps #-} basicOverlaps (MV_Mint v1) (MV_Mint v2) = VGM.basicOverlaps v1 v2 {-# INLINE basicUnsafeNew #-} basicUnsafeNew n = MV_Mint `fmap` VGM.basicUnsafeNew n {-# INLINE basicInitialize #-} basicInitialize (MV_Mint v) = VGM.basicInitialize v {-# INLINE basicUnsafeReplicate #-} basicUnsafeReplicate n x = MV_Mint `fmap` VGM.basicUnsafeReplicate n (coerce x) {-# INLINE basicUnsafeRead #-} basicUnsafeRead (MV_Mint v) i = coerce `fmap` VGM.basicUnsafeRead v i {-# INLINE basicUnsafeWrite #-} basicUnsafeWrite (MV_Mint v) i x = VGM.basicUnsafeWrite v i (coerce x) {-# INLINE basicClear #-} basicClear (MV_Mint v) = VGM.basicClear v {-# INLINE basicSet #-} basicSet (MV_Mint v) x = VGM.basicSet v (coerce x) {-# INLINE basicUnsafeCopy #-} basicUnsafeCopy (MV_Mint v1) (MV_Mint v2) = VGM.basicUnsafeCopy v1 v2 {-# INLINE basicUnsafeMove #-} basicUnsafeMove (MV_Mint v1) (MV_Mint v2) = VGM.basicUnsafeMove v1 v2 {-# INLINE basicUnsafeGrow #-} basicUnsafeGrow (MV_Mint v) n = MV_Mint `fmap` VGM.basicUnsafeGrow v n instance VG.Vector VU.Vector Mint where {-# INLINE basicUnsafeFreeze #-} basicUnsafeFreeze (MV_Mint v) = V_Mint `fmap` VG.basicUnsafeFreeze v {-# INLINE basicUnsafeThaw #-} basicUnsafeThaw (V_Mint v) = MV_Mint `fmap` VG.basicUnsafeThaw v {-# INLINE basicLength #-} basicLength (V_Mint v) = VG.basicLength v {-# INLINE basicUnsafeSlice #-} basicUnsafeSlice i n (V_Mint v) = V_Mint $ VG.basicUnsafeSlice i n v {-# INLINE basicUnsafeIndexM #-} basicUnsafeIndexM (V_Mint v) i = coerce `fmap` VG.basicUnsafeIndexM v i basicUnsafeCopy (MV_Mint mv) (V_Mint v) = VG.basicUnsafeCopy mv v {-# INLINE elemseq #-} elemseq _ = seq intMod :: (Integral int) => int -> Mint intMod x = fromIntegral $ mod (fromIntegral x) MOD {-# INLINE intMod #-} mintValidate :: Mint -> Bool mintValidate (Mint x) = 0 <= x && x < MOD {-# INLINE mintValidate #-} -- utils {-# INLINE fact #-} fact :: Int -> Mint fact = VU.unsafeIndex factCache {-# INLINE recipFact #-} recipFact :: Int -> Mint recipFact = VU.unsafeIndex recipFactCache {-# INLINE perm #-} perm :: Int -> Int -> Mint perm n k | n < k = 0 | otherwise = fact n * recipFact k {-# INLINE comb #-} comb :: Int -> Int -> Mint comb n k | n < k = Mint 0 | otherwise = fact n * recipFact (n - k) * recipFact k #define FACT_CACHE_SIZE 2000000 {-# INLINE factCacheSize #-} factCacheSize :: Int factCacheSize = min (modulus - 1) FACT_CACHE_SIZE {-# NOINLINE factCache #-} factCache :: VU.Vector Mint factCache = VU.scanl' (\ x y -> x * coerce y) (1 :: Mint) $ VU.generate factCacheSize (+ 1) {-# NOINLINE recipFactCache #-} recipFactCache :: VU.Vector Mint recipFactCache = VU.scanr' ((*) . coerce) (1 / factCache VU.! factCacheSize) $ VU.generate factCacheSize (+ 1) powN :: Int -> VU.Vector Mint powN n = VU.scanl' (\acc x -> acc * intMod x) 1 $ VU.replicate factCacheSize n 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 pint :: StateT BSC8.ByteString Maybe Int pint = coerce $ BSC8.readInt . BSC8.dropWhile Char.isSpace 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 = VU.unzip . VU.unfoldrN n (runStateT $ (,) <$> pint <*> pint) <$> BSC8.getContents parseANBNCN :: Int -> IO (VU.Vector Int, VU.Vector Int, VU.Vector Int) parseANBNCN n = VU.unzip3 . VU.unfoldrN n (runStateT $ (,,) <$> pint <*> pint <*> pint) <$> BSC8.getContents main :: IO () main = do (n, m, a, b) <- parse4 if 1 + a * (n - 1) > m || a * (n - 1) > b then print 0 else print $ solver n m a b solver :: Int -> Int -> Int -> Int -> Int solver n m a b = coerce $ ans * (fact n) where ans = loop 1 0 where loop s ret | s == (m + 1) = ret | s + a * (n - 1) > m = ret | otherwise = loop (s + 1) ret' where ret' = ret + comb ((min m (s + b)) - s - (a - 1) * (n - 1)) (n - 1)