.gitignore

.stack-work/
dist-new/
dist-newstyle/
misc.cabal
*.log
core
*.hi
*.o
*~

Modular.hs

{-# LANGUAGE ImplicitParams #-}
module Modular where

import Control.Arrow

newtype ModInt = ModInt Int deriving (Eq, Ord, Enum)

modulus :: Int
modulus = 998244353

toModInt :: Int -> ModInt
toModInt n = ModInt (n `mod` modulus)

instance Num ModInt where
    ModInt a + ModInt b = ModInt ((a + b) `mod` modulus)
    ModInt a - ModInt b = ModInt ((a - b) `mod` modulus)
    ModInt a * ModInt b = ModInt ((a * b) `mod` modulus)
    abs (ModInt a) = ModInt (abs a)
    signum (ModInt a) = ModInt (signum a)
    fromInteger n = ModInt $ fromInteger (n `mod` fromIntegral modulus)

instance Real ModInt where
    toRational (ModInt a) = toRational a

instance Integral ModInt where
    quotRem a b = (a * inv b, 0)
    toInteger (ModInt a) = toInteger a

inv :: ModInt -> ModInt
inv a = a ^ (modulus - 2)

instance Show ModInt where
    show (ModInt a) = show a

instance Read ModInt where
    readsPrec _ = map (first fromInteger) . readsPrec  0