{-# LANGUAGE CPP #-}
{-# LANGUAGE DerivingStrategies #-}
{-# LANGUAGE MagicHash #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE UnboxedTuples #-}

module Data.IntMod where

import Data.Bits
import Data.Coerce
import Data.Primitive
import Data.Ratio
import qualified Data.Vector.Generic as G
import qualified Data.Vector.Generic.Mutable as GM
import qualified Data.Vector.Unboxed as U
import GHC.Exts

#define MOD 1000000007

modulus :: (Num a) => a
modulus :: forall a. Num a => a
modulus = MOD
{-# INLINE modulus #-}

infixr 8 ^%
infixl 7 *%, /%
infixl 6 +%, -%

(+%) :: Int -> Int -> Int
(I# Int#
x#) +% :: Int -> Int -> Int
+% (I# Int#
y#) = case Int#
x# Int# -> Int# -> Int#
+# Int#
y# of
  Int#
r# -> Int# -> Int
I# (Int#
r# Int# -> Int# -> Int#
-# ((Int#
r# Int# -> Int# -> Int#
>=# MOD#) *# MOD#))
{-# INLINE (+%) #-}

(-%) :: Int -> Int -> Int
(I# Int#
x#) -% :: Int -> Int -> Int
-% (I# Int#
y#) = case Int#
x# Int# -> Int# -> Int#
-# Int#
y# of
  Int#
r# -> Int# -> Int
I# (Int#
r# Int# -> Int# -> Int#
+# ((Int#
r# Int# -> Int# -> Int#
<# Int#
0#) Int# -> Int# -> Int#
*# MOD#))
{-# INLINE (-%) #-}

(*%) :: Int -> Int -> Int
(I# Int#
x#) *% :: Int -> Int -> Int
*% (I# Int#
y#) = case Word# -> Word# -> Word#
timesWord# (Int# -> Word#
int2Word# Int#
x#) (Int# -> Word#
int2Word# Int#
y#) of
  Word#
z# -> case Word# -> Word# -> (# Word#, Word# #)
timesWord2# Word#
z# Word#
im# of
    (# Word#
q#, Word#
_ #) -> case Word# -> Word# -> Word#
minusWord# Word#
z# (Word# -> Word# -> Word#
timesWord# Word#
q# Word#
m#) of
      Word#
v#
        | Int# -> Bool
isTrue# (Word# -> Word# -> Int#
geWord# Word#
v# Word#
m#) -> Int# -> Int
I# (Word# -> Int#
word2Int# (Word# -> Word# -> Word#
plusWord# Word#
v# Word#
m#))
        | Bool
otherwise -> Int# -> Int
I# (Word# -> Int#
word2Int# Word#
v#)
  where
    m# :: Word#
m# = Int# -> Word#
int2Word# MOD#
    im# :: Word#
im# = Word# -> Word# -> Word#
plusWord# (Word# -> Word# -> Word#
quotWord# Word#
0xffffffffffffffff## Word#
m#) Word#
1##
{-# INLINE (*%) #-}

{- |
>>> 1 /% 0
0
-}
(/%) :: Int -> Int -> Int
(I# Int#
x#) /% :: Int -> Int -> Int
/% (I# Int#
y#) = Int# -> Int# -> Int# -> Int# -> Int
go# Int#
y# MOD# 1# 0#
  where
    go# :: Int# -> Int# -> Int# -> Int# -> Int
go# Int#
a# Int#
b# Int#
u# Int#
v#
      | Int# -> Bool
isTrue# (Int#
b# Int# -> Int# -> Int#
># Int#
0#) = case Int#
a# Int# -> Int# -> Int#
`quotInt#` Int#
b# of
          Int#
q# -> Int# -> Int# -> Int# -> Int# -> Int
go# Int#
b# (Int#
a# Int# -> Int# -> Int#
-# (Int#
q# Int# -> Int# -> Int#
*# Int#
b#)) Int#
v# (Int#
u# Int# -> Int# -> Int#
-# (Int#
q# Int# -> Int# -> Int#
*# Int#
v#))
      | Bool
otherwise = Int# -> Int
I# ((Int#
x# Int# -> Int# -> Int#
*# (Int#
u# Int# -> Int# -> Int#
+# MOD#)) `remInt#` MOD#)
{-# INLINE (/%) #-}

(^%) :: Int -> Int -> Int
Int
x ^% :: Int -> Int -> Int
^% Int
n
  | Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0 = Int -> Int -> Int -> Int
forall {a}. (Bits a, Num a) => Int -> Int -> a -> Int
go Int
1 Int
x Int
n
  | Int
n Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0 = Int
1
  | Bool
otherwise = Int -> Int -> Int -> Int
forall {a}. (Bits a, Num a) => Int -> Int -> a -> Int
go Int
1 (Int
1 Int -> Int -> Int
/% Int
x) (-Int
n)
  where
    go :: Int -> Int -> a -> Int
go !Int
acc !Int
y !a
m
      | a
m a -> a -> a
forall a. Bits a => a -> a -> a
.&. a
1 a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
0 = Int -> Int -> a -> Int
go Int
acc (Int
y Int -> Int -> Int
*% Int
y) (a -> Int -> a
forall a. Bits a => a -> Int -> a
unsafeShiftR a
m Int
1)
      | a
m a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
1 = Int
acc Int -> Int -> Int
*% Int
y
      | Bool
otherwise = Int -> Int -> a -> Int
go (Int
acc Int -> Int -> Int
*% Int
y) (Int
y Int -> Int -> Int
*% Int
y) (a -> Int -> a
forall a. Bits a => a -> Int -> a
unsafeShiftR (a
m a -> a -> a
forall a. Num a => a -> a -> a
- a
1) Int
1)

newtype IntMod = IntMod {IntMod -> Int
getIntMod :: Int}
  deriving newtype (IntMod -> IntMod -> Bool
(IntMod -> IntMod -> Bool)
-> (IntMod -> IntMod -> Bool) -> Eq IntMod
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: IntMod -> IntMod -> Bool
== :: IntMod -> IntMod -> Bool
$c/= :: IntMod -> IntMod -> Bool
/= :: IntMod -> IntMod -> Bool
Eq, Eq IntMod
Eq IntMod =>
(IntMod -> IntMod -> Ordering)
-> (IntMod -> IntMod -> Bool)
-> (IntMod -> IntMod -> Bool)
-> (IntMod -> IntMod -> Bool)
-> (IntMod -> IntMod -> Bool)
-> (IntMod -> IntMod -> IntMod)
-> (IntMod -> IntMod -> IntMod)
-> Ord IntMod
IntMod -> IntMod -> Bool
IntMod -> IntMod -> Ordering
IntMod -> IntMod -> IntMod
forall a.
Eq a =>
(a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
$ccompare :: IntMod -> IntMod -> Ordering
compare :: IntMod -> IntMod -> Ordering
$c< :: IntMod -> IntMod -> Bool
< :: IntMod -> IntMod -> Bool
$c<= :: IntMod -> IntMod -> Bool
<= :: IntMod -> IntMod -> Bool
$c> :: IntMod -> IntMod -> Bool
> :: IntMod -> IntMod -> Bool
$c>= :: IntMod -> IntMod -> Bool
>= :: IntMod -> IntMod -> Bool
$cmax :: IntMod -> IntMod -> IntMod
max :: IntMod -> IntMod -> IntMod
$cmin :: IntMod -> IntMod -> IntMod
min :: IntMod -> IntMod -> IntMod
Ord, ReadPrec [IntMod]
ReadPrec IntMod
Int -> ReadS IntMod
ReadS [IntMod]
(Int -> ReadS IntMod)
-> ReadS [IntMod]
-> ReadPrec IntMod
-> ReadPrec [IntMod]
-> Read IntMod
forall a.
(Int -> ReadS a)
-> ReadS [a] -> ReadPrec a -> ReadPrec [a] -> Read a
$creadsPrec :: Int -> ReadS IntMod
readsPrec :: Int -> ReadS IntMod
$creadList :: ReadS [IntMod]
readList :: ReadS [IntMod]
$creadPrec :: ReadPrec IntMod
readPrec :: ReadPrec IntMod
$creadListPrec :: ReadPrec [IntMod]
readListPrec :: ReadPrec [IntMod]
Read, Int -> IntMod -> ShowS
[IntMod] -> ShowS
IntMod -> String
(Int -> IntMod -> ShowS)
-> (IntMod -> String) -> ([IntMod] -> ShowS) -> Show IntMod
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> IntMod -> ShowS
showsPrec :: Int -> IntMod -> ShowS
$cshow :: IntMod -> String
show :: IntMod -> String
$cshowList :: [IntMod] -> ShowS
showList :: [IntMod] -> ShowS
Show, Num IntMod
Ord IntMod
(Num IntMod, Ord IntMod) => (IntMod -> Rational) -> Real IntMod
IntMod -> Rational
forall a. (Num a, Ord a) => (a -> Rational) -> Real a
$ctoRational :: IntMod -> Rational
toRational :: IntMod -> Rational
Real, Addr# -> Int# -> IntMod
ByteArray# -> Int# -> IntMod
IntMod -> Int#
(IntMod -> Int#)
-> (IntMod -> Int#)
-> (ByteArray# -> Int# -> IntMod)
-> (forall s.
    MutableByteArray# s -> Int# -> State# s -> (# State# s, IntMod #))
-> (forall s.
    MutableByteArray# s -> Int# -> IntMod -> State# s -> State# s)
-> (forall s.
    MutableByteArray# s
    -> Int# -> Int# -> IntMod -> State# s -> State# s)
-> (Addr# -> Int# -> IntMod)
-> (forall s. Addr# -> Int# -> State# s -> (# State# s, IntMod #))
-> (forall s. Addr# -> Int# -> IntMod -> State# s -> State# s)
-> (forall s.
    Addr# -> Int# -> Int# -> IntMod -> State# s -> State# s)
-> Prim IntMod
forall s. Addr# -> Int# -> Int# -> IntMod -> State# s -> State# s
forall s. Addr# -> Int# -> State# s -> (# State# s, IntMod #)
forall s. Addr# -> Int# -> IntMod -> State# s -> State# s
forall s.
MutableByteArray# s
-> Int# -> Int# -> IntMod -> State# s -> State# s
forall s.
MutableByteArray# s -> Int# -> State# s -> (# State# s, IntMod #)
forall s.
MutableByteArray# s -> Int# -> IntMod -> State# s -> State# s
forall a.
(a -> Int#)
-> (a -> Int#)
-> (ByteArray# -> Int# -> a)
-> (forall s.
    MutableByteArray# s -> Int# -> State# s -> (# State# s, a #))
-> (forall s.
    MutableByteArray# s -> Int# -> a -> State# s -> State# s)
-> (forall s.
    MutableByteArray# s -> Int# -> Int# -> a -> State# s -> State# s)
-> (Addr# -> Int# -> a)
-> (forall s. Addr# -> Int# -> State# s -> (# State# s, a #))
-> (forall s. Addr# -> Int# -> a -> State# s -> State# s)
-> (forall s. Addr# -> Int# -> Int# -> a -> State# s -> State# s)
-> Prim a
$csizeOf# :: IntMod -> Int#
sizeOf# :: IntMod -> Int#
$calignment# :: IntMod -> Int#
alignment# :: IntMod -> Int#
$cindexByteArray# :: ByteArray# -> Int# -> IntMod
indexByteArray# :: ByteArray# -> Int# -> IntMod
$creadByteArray# :: forall s.
MutableByteArray# s -> Int# -> State# s -> (# State# s, IntMod #)
readByteArray# :: forall s.
MutableByteArray# s -> Int# -> State# s -> (# State# s, IntMod #)
$cwriteByteArray# :: forall s.
MutableByteArray# s -> Int# -> IntMod -> State# s -> State# s
writeByteArray# :: forall s.
MutableByteArray# s -> Int# -> IntMod -> State# s -> State# s
$csetByteArray# :: forall s.
MutableByteArray# s
-> Int# -> Int# -> IntMod -> State# s -> State# s
setByteArray# :: forall s.
MutableByteArray# s
-> Int# -> Int# -> IntMod -> State# s -> State# s
$cindexOffAddr# :: Addr# -> Int# -> IntMod
indexOffAddr# :: Addr# -> Int# -> IntMod
$creadOffAddr# :: forall s. Addr# -> Int# -> State# s -> (# State# s, IntMod #)
readOffAddr# :: forall s. Addr# -> Int# -> State# s -> (# State# s, IntMod #)
$cwriteOffAddr# :: forall s. Addr# -> Int# -> IntMod -> State# s -> State# s
writeOffAddr# :: forall s. Addr# -> Int# -> IntMod -> State# s -> State# s
$csetOffAddr# :: forall s. Addr# -> Int# -> Int# -> IntMod -> State# s -> State# s
setOffAddr# :: forall s. Addr# -> Int# -> Int# -> IntMod -> State# s -> State# s
Prim)

intMod :: (Integral a) => a -> IntMod
intMod :: forall a. Integral a => a -> IntMod
intMod a
x = Integer -> IntMod
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Integer -> IntMod) -> Integer -> IntMod
forall a b. (a -> b) -> a -> b
$ Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
mod (a -> Integer
forall a. Integral a => a -> Integer
toInteger a
x) MOD
{-# INLINE intMod #-}

intModValidate :: IntMod -> Bool
intModValidate :: IntMod -> Bool
intModValidate (IntMod Int
x) = Int
0 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
x Bool -> Bool -> Bool
&& Int
x Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< MOD
{-# INLINE intModValidate #-}

instance Bounded IntMod where
  minBound :: IntMod
minBound = Int -> IntMod
IntMod Int
0
  maxBound :: IntMod
maxBound = Int -> IntMod
IntMod (Int -> IntMod) -> Int -> IntMod
forall a b. (a -> b) -> a -> b
$ Int
forall a. Num a => a
modulus Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1

instance Enum IntMod where
  toEnum :: Int -> IntMod
toEnum = Int -> IntMod
forall a. Integral a => a -> IntMod
intMod
  fromEnum :: IntMod -> Int
fromEnum = IntMod -> Int
forall a b. Coercible a b => a -> b
coerce

instance Integral IntMod where
  quotRem :: IntMod -> IntMod -> (IntMod, IntMod)
quotRem IntMod
x IntMod
y = (IntMod
x IntMod -> IntMod -> IntMod
forall a. Fractional a => a -> a -> a
/ IntMod
y, IntMod
x IntMod -> IntMod -> IntMod
forall a. Num a => a -> a -> a
- IntMod
x IntMod -> IntMod -> IntMod
forall a. Fractional a => a -> a -> a
/ IntMod
y IntMod -> IntMod -> IntMod
forall a. Num a => a -> a -> a
* IntMod
y)
  toInteger :: IntMod -> Integer
toInteger = (Int -> Integer) -> IntMod -> Integer
forall a b. Coercible a b => a -> b
coerce (forall a. Integral a => a -> Integer
toInteger @Int)

instance Num IntMod where
  + :: IntMod -> IntMod -> IntMod
(+) = (Int -> Int -> Int) -> IntMod -> IntMod -> IntMod
forall a b. Coercible a b => a -> b
coerce Int -> Int -> Int
(+%)
  (-) = (Int -> Int -> Int) -> IntMod -> IntMod -> IntMod
forall a b. Coercible a b => a -> b
coerce Int -> Int -> Int
(-%)
  * :: IntMod -> IntMod -> IntMod
(*) = (Int -> Int -> Int) -> IntMod -> IntMod -> IntMod
forall a b. Coercible a b => a -> b
coerce Int -> Int -> Int
(*%)
  abs :: IntMod -> IntMod
abs = IntMod -> IntMod
forall a. a -> a
id
  signum :: IntMod -> IntMod
signum = IntMod -> IntMod -> IntMod
forall a b. a -> b -> a
const (Int -> IntMod
IntMod Int
1)
  fromInteger :: Integer -> IntMod
fromInteger Integer
x = forall a b. Coercible a b => a -> b
forall a b. Coercible a b => a -> b
coerce @Int @IntMod (Int -> IntMod) -> (Integer -> Int) -> Integer -> IntMod
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Integer -> Int
forall a. Num a => Integer -> a
fromInteger (Integer -> IntMod) -> Integer -> IntMod
forall a b. (a -> b) -> a -> b
$ Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
mod Integer
x Integer
forall a. Num a => a
modulus

instance Fractional IntMod where
  / :: IntMod -> IntMod -> IntMod
(/) = (Int -> Int -> Int) -> IntMod -> IntMod -> IntMod
forall a b. Coercible a b => a -> b
coerce Int -> Int -> Int
(/%)
  fromRational :: Rational -> IntMod
fromRational Rational
q = Integer -> IntMod
forall a. Num a => Integer -> a
fromInteger (Rational -> Integer
forall a. Ratio a -> a
numerator Rational
q) IntMod -> IntMod -> IntMod
forall a. Fractional a => a -> a -> a
/ Integer -> IntMod
forall a. Num a => Integer -> a
fromInteger (Rational -> Integer
forall a. Ratio a -> a
denominator Rational
q)

newtype instance U.MVector s IntMod = MV_IntMod (U.MVector s Int)
newtype instance U.Vector IntMod = V_IntMod (U.Vector Int)
deriving newtype instance GM.MVector U.MVector IntMod
deriving newtype instance G.Vector U.Vector IntMod
instance U.Unbox IntMod