{-# LANGUAGE MagicHash #-}
{-# LANGUAGE TypeFamilies #-}

-- | It is the structure that treats the modular arithmetic. All the remaining parts of AC Library
-- works without modint, so you don't necessarily read this to use the remaining parts.
--
-- ==== __Example__
-- It is often convenient to define a type alias of `ModInt` for a specific modulus value:
--
-- >>> import AtCoder.ModInt qualified as M
-- >>> type Mint = M.ModInt998244353
-- >>> let modInt :: Int -> Mint; modInt = M.new
-- >>> modInt 1000000000
-- 1755647
--
-- >>> modInt 1000000000 / modInt 3
-- 666081451
--
-- ==== Major changes from the original @ac-library@
-- - @StaticModInt@ is renamed to `ModInt`.
-- - @DynamicModInt@ is removed.
--
-- @since 1.0.0.0
module AtCoder.ModInt
  ( -- * Modulus
    Modulus (..),
    ModInt998244353,
    ModInt1000000007,

    -- ** Helpers
    modVal,
    modVal#,

    -- * ModInt
    ModInt (..),

    -- * Constructors

    -- ** Safe constructors
    new,
    new32,
    new64,

    -- ** Unsafe constructor
    unsafeNew,

    -- * Accessors

    -- ** Modulus value
    modulus,

    -- ** Internal value
    val,
    val32,
    val64,

    -- * Operators
    pow,
    inv,
  )
where

import AtCoder.Internal.Assert qualified as ACIA
import AtCoder.Internal.Barrett qualified as ACIBT
import AtCoder.Internal.Math qualified as ACIM
import Data.Bits ((!>>.))
import Data.Coerce (coerce)
import Data.Proxy (Proxy)
import Data.Ratio (denominator, numerator)
import Data.Vector.Generic qualified as VG
import Data.Vector.Generic.Mutable qualified as VGM
import Data.Vector.Primitive qualified as P
import Data.Vector.Unboxed qualified as U
import Data.Vector.Unboxed qualified as VU
import Data.Word (Word32, Word64)
import GHC.Exts (Proxy#, proxy#)
import GHC.Stack (HasCallStack)
import GHC.TypeNats (KnownNat, natVal, natVal')

-- | `KnownNat` with meta information used for modulus.
--
-- @since 1.0.0.0
class (KnownNat a) => Modulus a where
  -- | Returns if the modulus is a prime value.
  --
  -- @since 1.0.0.0
  isPrimeModulus :: Proxy# a -> Bool

  -- | Returns the primitive root of the modulus value. Note that the default implementation is slow
  -- and the value should be hard-coded.
  --
  -- @since 1.0.0.0
  {-# INLINE primitiveRootModulus #-}
  primitiveRootModulus :: Proxy# a -> Int
  -- we could use `AllowAmbigousTypes` or `Tagged` newtype, but `Proxy#` wasn't so slow.
  -- not sure about the case of `x^n` though..
  primitiveRootModulus Proxy# a
_ = Int -> Int
ACIM.primitiveRoot (Int -> Int) -> Int -> Int
forall a b. (a -> b) -> a -> b
$ Nat -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Proxy# a -> Nat
forall (n :: Nat). KnownNat n => Proxy# n -> Nat
natVal' (forall (a :: Nat). Proxy# a
forall {k} (a :: k). Proxy# a
proxy# @a))

-- | \(2^{24} - 1\).
--
-- @since 1.0.0.0
instance Modulus 167772161 where
  {-# INLINE isPrimeModulus #-}
  isPrimeModulus :: Proxy# 167772161 -> Bool
isPrimeModulus Proxy# 167772161
_ = Bool
True
  {-# INLINE primitiveRootModulus #-}
  primitiveRootModulus :: Proxy# 167772161 -> Int
primitiveRootModulus Proxy# 167772161
_ = Int
3

-- | \(2^{25} - 1\).
--
-- @since 1.0.0.0
instance Modulus 469762049 where
  {-# INLINE isPrimeModulus #-}
  isPrimeModulus :: Proxy# 469762049 -> Bool
isPrimeModulus Proxy# 469762049
_ = Bool
True
  {-# INLINE primitiveRootModulus #-}
  primitiveRootModulus :: Proxy# 469762049 -> Int
primitiveRootModulus Proxy# 469762049
_ = Int
3

-- | \(2^{26} - 1\).
--
-- @since 1.0.0.0
instance Modulus 754974721 where
  {-# INLINE isPrimeModulus #-}
  isPrimeModulus :: Proxy# 754974721 -> Bool
isPrimeModulus Proxy# 754974721
_ = Bool
True
  {-# INLINE primitiveRootModulus #-}
  primitiveRootModulus :: Proxy# 754974721 -> Int
primitiveRootModulus Proxy# 754974721
_ = Int
11

-- | \(119 \times 2^{23} + 1\). It is often used in contest problems.
--
-- @since 1.0.0.0
instance Modulus 998244353 where
  {-# INLINE isPrimeModulus #-}
  isPrimeModulus :: Proxy# 998244353 -> Bool
isPrimeModulus Proxy# 998244353
_ = Bool
True
  {-# INLINE primitiveRootModulus #-}
  primitiveRootModulus :: Proxy# 998244353 -> Int
primitiveRootModulus Proxy# 998244353
_ = Int
3

-- | It used to be used in contest problems.
--
-- @since 1.0.0.0
instance Modulus 1000000007 where
  {-# INLINE isPrimeModulus #-}
  isPrimeModulus :: Proxy# 1000000007 -> Bool
isPrimeModulus Proxy# 1000000007
_ = Bool
True
  {-# INLINE primitiveRootModulus #-}
  primitiveRootModulus :: Proxy# 1000000007 -> Int
primitiveRootModulus Proxy# 1000000007
_ = Int
5

-- | \(2^{31} - 1\), suitable for boundary testing.
--
-- @since 1.0.0.0
instance Modulus 2147483647 where
  {-# INLINE isPrimeModulus #-}
  isPrimeModulus :: Proxy# 2147483647 -> Bool
isPrimeModulus Proxy# 2147483647
_ = Bool
True
  {-# INLINE primitiveRootModulus #-}
  primitiveRootModulus :: Proxy# 2147483647 -> Int
primitiveRootModulus Proxy# 2147483647
_ = Int
7

-- | @since 1.0.0.0
type ModInt998244353 = ModInt 998244353

-- | @since 1.0.0.0
type ModInt1000000007 = ModInt 1000000007

-- | Retrieves the `Int` value from a `KnownNat`.
--
-- >>> import Data.Proxy (Proxy(..))
-- >>> modVal (Proxy @42)
-- 42
--
-- @since 1.0.0.0
{-# INLINE modVal #-}
modVal :: forall a. (KnownNat a) => Proxy a -> Int
modVal :: forall (a :: Nat). KnownNat a => Proxy a -> Int
modVal Proxy a
p = Nat -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Nat -> Int) -> Nat -> Int
forall a b. (a -> b) -> a -> b
$ Proxy a -> Nat
forall (n :: Nat) (proxy :: Nat -> *). KnownNat n => proxy n -> Nat
natVal Proxy a
p

-- | Retrieves the `Int` value from a `KnownNat`.
--
-- >>> :set -XMagicHash
-- >>> import GHC.Exts (proxy#)
-- >>> modVal# (proxy# @42)
-- 42
--
-- @since 1.0.0.0
{-# INLINE modVal# #-}
modVal# :: forall a. (KnownNat a) => Proxy# a -> Int
modVal# :: forall (a :: Nat). KnownNat a => Proxy# a -> Int
modVal# Proxy# a
p = Nat -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Nat -> Int) -> Nat -> Int
forall a b. (a -> b) -> a -> b
$ Proxy# a -> Nat
forall (n :: Nat). KnownNat n => Proxy# n -> Nat
natVal' Proxy# a
p

-- | Creates a `ModInt` from an `Int` value taking the mod.
--
-- @since 1.0.0.0
{-# INLINE new #-}
new :: forall a. (KnownNat a) => Int -> ModInt a
new :: forall (a :: Nat). KnownNat a => Int -> ModInt a
new Int
v = Word32 -> ModInt a
forall {k} (a :: k). Word32 -> ModInt a
ModInt (Word32 -> ModInt a) -> (Int -> Word32) -> Int -> ModInt a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Word32
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int -> ModInt a) -> Int -> ModInt a
forall a b. (a -> b) -> a -> b
$ Int
v Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` Nat -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Proxy# a -> Nat
forall (n :: Nat). KnownNat n => Proxy# n -> Nat
natVal' (forall (a :: Nat). Proxy# a
forall {k} (a :: k). Proxy# a
proxy# @a))

-- | Creates a `ModInt` from a `Word32` value taking the mod.
--
-- @since 1.0.0.0
{-# INLINE new32 #-}
new32 :: forall a. (KnownNat a) => Word32 -> ModInt a
new32 :: forall (a :: Nat). KnownNat a => Word32 -> ModInt a
new32 Word32
v = Word32 -> ModInt a
forall {k} (a :: k). Word32 -> ModInt a
ModInt (Word32 -> ModInt a) -> Word32 -> ModInt a
forall a b. (a -> b) -> a -> b
$ Word32
v Word32 -> Word32 -> Word32
forall a. Integral a => a -> a -> a
`mod` Nat -> Word32
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Proxy# a -> Nat
forall (n :: Nat). KnownNat n => Proxy# n -> Nat
natVal' (forall (a :: Nat). Proxy# a
forall {k} (a :: k). Proxy# a
proxy# @a))

-- | Creates a `ModInt` from a `Word64` value taking the mod.
--
-- @since 1.0.0.0
{-# INLINE new64 #-}
new64 :: forall a. (KnownNat a) => Word64 -> ModInt a
new64 :: forall (a :: Nat). KnownNat a => Word64 -> ModInt a
new64 Word64
v = Word32 -> ModInt a
forall {k} (a :: k). Word32 -> ModInt a
ModInt (Word32 -> ModInt a) -> (Word64 -> Word32) -> Word64 -> ModInt a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Word64 -> Word32
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Word64 -> ModInt a) -> Word64 -> ModInt a
forall a b. (a -> b) -> a -> b
$ Word64
v Word64 -> Word64 -> Word64
forall a. Integral a => a -> a -> a
`mod` Nat -> Word64
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Proxy# a -> Nat
forall (n :: Nat). KnownNat n => Proxy# n -> Nat
natVal' (forall (a :: Nat). Proxy# a
forall {k} (a :: k). Proxy# a
proxy# @a))

-- | Creates `ModInt` without taking the mod. It is the function for constant-factor speedup.
--
-- ==== Constraints
-- - \(0 \leq x \lt \mathrm{mod}\) (not asserted at runtime)
--
-- @since 1.0.0.0
{-# INLINE unsafeNew #-}
unsafeNew :: (KnownNat a) => Word32 -> ModInt a
unsafeNew :: forall (a :: Nat). KnownNat a => Word32 -> ModInt a
unsafeNew = Word32 -> ModInt a
forall {k} (a :: k). Word32 -> ModInt a
ModInt

-- | `Word32` value that treats the modular arithmetic.
newtype ModInt a = ModInt
  { -- | @since 1.0.0.0
    forall {k} (a :: k). ModInt a -> Word32
unModInt :: Word32
  }
  deriving
    ( -- | @since 1.0.0.0
      Addr# -> Int# -> ModInt a
ByteArray# -> Int# -> ModInt a
Proxy (ModInt a) -> Int#
ModInt a -> Int#
(Proxy (ModInt a) -> Int#)
-> (ModInt a -> Int#)
-> (Proxy (ModInt a) -> Int#)
-> (ModInt a -> Int#)
-> (ByteArray# -> Int# -> ModInt a)
-> (forall s.
    MutableByteArray# s
    -> Int# -> State# s -> (# State# s, ModInt a #))
-> (forall s.
    MutableByteArray# s -> Int# -> ModInt a -> State# s -> State# s)
-> (forall s.
    MutableByteArray# s
    -> Int# -> Int# -> ModInt a -> State# s -> State# s)
-> (Addr# -> Int# -> ModInt a)
-> (forall s.
    Addr# -> Int# -> State# s -> (# State# s, ModInt a #))
-> (forall s. Addr# -> Int# -> ModInt a -> State# s -> State# s)
-> (forall s.
    Addr# -> Int# -> Int# -> ModInt a -> State# s -> State# s)
-> Prim (ModInt a)
forall s. Addr# -> Int# -> Int# -> ModInt a -> State# s -> State# s
forall s. Addr# -> Int# -> State# s -> (# State# s, ModInt a #)
forall s. Addr# -> Int# -> ModInt a -> State# s -> State# s
forall s.
MutableByteArray# s
-> Int# -> Int# -> ModInt a -> State# s -> State# s
forall s.
MutableByteArray# s -> Int# -> State# s -> (# State# s, ModInt a #)
forall s.
MutableByteArray# s -> Int# -> ModInt a -> State# s -> State# s
forall a.
(Proxy a -> Int#)
-> (a -> Int#)
-> (Proxy 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
forall k (a :: k). Addr# -> Int# -> ModInt a
forall k (a :: k). ByteArray# -> Int# -> ModInt a
forall k (a :: k). Proxy (ModInt a) -> Int#
forall k (a :: k). ModInt a -> Int#
forall k (a :: k) s.
Addr# -> Int# -> Int# -> ModInt a -> State# s -> State# s
forall k (a :: k) s.
Addr# -> Int# -> State# s -> (# State# s, ModInt a #)
forall k (a :: k) s.
Addr# -> Int# -> ModInt a -> State# s -> State# s
forall k (a :: k) s.
MutableByteArray# s
-> Int# -> Int# -> ModInt a -> State# s -> State# s
forall k (a :: k) s.
MutableByteArray# s -> Int# -> State# s -> (# State# s, ModInt a #)
forall k (a :: k) s.
MutableByteArray# s -> Int# -> ModInt a -> State# s -> State# s
$csizeOfType# :: forall k (a :: k). Proxy (ModInt a) -> Int#
sizeOfType# :: Proxy (ModInt a) -> Int#
$csizeOf# :: forall k (a :: k). ModInt a -> Int#
sizeOf# :: ModInt a -> Int#
$calignmentOfType# :: forall k (a :: k). Proxy (ModInt a) -> Int#
alignmentOfType# :: Proxy (ModInt a) -> Int#
$calignment# :: forall k (a :: k). ModInt a -> Int#
alignment# :: ModInt a -> Int#
$cindexByteArray# :: forall k (a :: k). ByteArray# -> Int# -> ModInt a
indexByteArray# :: ByteArray# -> Int# -> ModInt a
$creadByteArray# :: forall k (a :: k) s.
MutableByteArray# s -> Int# -> State# s -> (# State# s, ModInt a #)
readByteArray# :: forall s.
MutableByteArray# s -> Int# -> State# s -> (# State# s, ModInt a #)
$cwriteByteArray# :: forall k (a :: k) s.
MutableByteArray# s -> Int# -> ModInt a -> State# s -> State# s
writeByteArray# :: forall s.
MutableByteArray# s -> Int# -> ModInt a -> State# s -> State# s
$csetByteArray# :: forall k (a :: k) s.
MutableByteArray# s
-> Int# -> Int# -> ModInt a -> State# s -> State# s
setByteArray# :: forall s.
MutableByteArray# s
-> Int# -> Int# -> ModInt a -> State# s -> State# s
$cindexOffAddr# :: forall k (a :: k). Addr# -> Int# -> ModInt a
indexOffAddr# :: Addr# -> Int# -> ModInt a
$creadOffAddr# :: forall k (a :: k) s.
Addr# -> Int# -> State# s -> (# State# s, ModInt a #)
readOffAddr# :: forall s. Addr# -> Int# -> State# s -> (# State# s, ModInt a #)
$cwriteOffAddr# :: forall k (a :: k) s.
Addr# -> Int# -> ModInt a -> State# s -> State# s
writeOffAddr# :: forall s. Addr# -> Int# -> ModInt a -> State# s -> State# s
$csetOffAddr# :: forall k (a :: k) s.
Addr# -> Int# -> Int# -> ModInt a -> State# s -> State# s
setOffAddr# :: forall s. Addr# -> Int# -> Int# -> ModInt a -> State# s -> State# s
P.Prim
    )
  deriving newtype
    ( -- | @since 1.0.0.0
      ModInt a -> ModInt a -> Bool
(ModInt a -> ModInt a -> Bool)
-> (ModInt a -> ModInt a -> Bool) -> Eq (ModInt a)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall k (a :: k). ModInt a -> ModInt a -> Bool
$c== :: forall k (a :: k). ModInt a -> ModInt a -> Bool
== :: ModInt a -> ModInt a -> Bool
$c/= :: forall k (a :: k). ModInt a -> ModInt a -> Bool
/= :: ModInt a -> ModInt a -> Bool
Eq,
      -- | @since 1.0.0.0
      Eq (ModInt a)
Eq (ModInt a) =>
(ModInt a -> ModInt a -> Ordering)
-> (ModInt a -> ModInt a -> Bool)
-> (ModInt a -> ModInt a -> Bool)
-> (ModInt a -> ModInt a -> Bool)
-> (ModInt a -> ModInt a -> Bool)
-> (ModInt a -> ModInt a -> ModInt a)
-> (ModInt a -> ModInt a -> ModInt a)
-> Ord (ModInt a)
ModInt a -> ModInt a -> Bool
ModInt a -> ModInt a -> Ordering
ModInt a -> ModInt a -> ModInt a
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
forall k (a :: k). Eq (ModInt a)
forall k (a :: k). ModInt a -> ModInt a -> Bool
forall k (a :: k). ModInt a -> ModInt a -> Ordering
forall k (a :: k). ModInt a -> ModInt a -> ModInt a
$ccompare :: forall k (a :: k). ModInt a -> ModInt a -> Ordering
compare :: ModInt a -> ModInt a -> Ordering
$c< :: forall k (a :: k). ModInt a -> ModInt a -> Bool
< :: ModInt a -> ModInt a -> Bool
$c<= :: forall k (a :: k). ModInt a -> ModInt a -> Bool
<= :: ModInt a -> ModInt a -> Bool
$c> :: forall k (a :: k). ModInt a -> ModInt a -> Bool
> :: ModInt a -> ModInt a -> Bool
$c>= :: forall k (a :: k). ModInt a -> ModInt a -> Bool
>= :: ModInt a -> ModInt a -> Bool
$cmax :: forall k (a :: k). ModInt a -> ModInt a -> ModInt a
max :: ModInt a -> ModInt a -> ModInt a
$cmin :: forall k (a :: k). ModInt a -> ModInt a -> ModInt a
min :: ModInt a -> ModInt a -> ModInt a
Ord,
      -- | @since 1.0.0.0
      ReadPrec [ModInt a]
ReadPrec (ModInt a)
Int -> ReadS (ModInt a)
ReadS [ModInt a]
(Int -> ReadS (ModInt a))
-> ReadS [ModInt a]
-> ReadPrec (ModInt a)
-> ReadPrec [ModInt a]
-> Read (ModInt a)
forall a.
(Int -> ReadS a)
-> ReadS [a] -> ReadPrec a -> ReadPrec [a] -> Read a
forall k (a :: k). ReadPrec [ModInt a]
forall k (a :: k). ReadPrec (ModInt a)
forall k (a :: k). Int -> ReadS (ModInt a)
forall k (a :: k). ReadS [ModInt a]
$creadsPrec :: forall k (a :: k). Int -> ReadS (ModInt a)
readsPrec :: Int -> ReadS (ModInt a)
$creadList :: forall k (a :: k). ReadS [ModInt a]
readList :: ReadS [ModInt a]
$creadPrec :: forall k (a :: k). ReadPrec (ModInt a)
readPrec :: ReadPrec (ModInt a)
$creadListPrec :: forall k (a :: k). ReadPrec [ModInt a]
readListPrec :: ReadPrec [ModInt a]
Read,
      -- | @since 1.0.0.0
      Int -> ModInt a -> ShowS
[ModInt a] -> ShowS
ModInt a -> String
(Int -> ModInt a -> ShowS)
-> (ModInt a -> String) -> ([ModInt a] -> ShowS) -> Show (ModInt a)
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
forall k (a :: k). Int -> ModInt a -> ShowS
forall k (a :: k). [ModInt a] -> ShowS
forall k (a :: k). ModInt a -> String
$cshowsPrec :: forall k (a :: k). Int -> ModInt a -> ShowS
showsPrec :: Int -> ModInt a -> ShowS
$cshow :: forall k (a :: k). ModInt a -> String
show :: ModInt a -> String
$cshowList :: forall k (a :: k). [ModInt a] -> ShowS
showList :: [ModInt a] -> ShowS
Show
    )

-- | Retrieve the mod from a `ModInt` object.
--
-- ==== Complecity
-- - \(O(1)\)
--
-- @since 1.0.0.0
{-# INLINE modulus #-}
modulus :: forall a. (KnownNat a) => ModInt a -> Int
modulus :: forall (a :: Nat). KnownNat a => ModInt a -> Int
modulus ModInt a
_ = Nat -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Proxy# a -> Nat
forall (n :: Nat). KnownNat n => Proxy# n -> Nat
natVal' (forall (a :: Nat). Proxy# a
forall {k} (a :: k). Proxy# a
proxy# @a))

-- | Returns the internal value converted to `Int`.
--
-- ==== Complecity
-- - \(O(1)\)
--
-- @since 1.0.0.0
{-# INLINE val #-}
val :: (KnownNat a) => ModInt a -> Int
val :: forall (a :: Nat). KnownNat a => ModInt a -> Int
val = Word32 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Word32 -> Int) -> (ModInt a -> Word32) -> ModInt a -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ModInt a -> Word32
forall {k} (a :: k). ModInt a -> Word32
unModInt

-- | Returns the internal value as `Word32` without type conversion. It is the function for
-- constant-factor speedup.
--
-- ==== Complecity
-- - \(O(1)\)
--
-- @since 1.0.0.0
{-# INLINE val32 #-}
val32 :: (KnownNat a) => ModInt a -> Word32
val32 :: forall (a :: Nat). KnownNat a => ModInt a -> Word32
val32 = ModInt a -> Word32
forall {k} (a :: k). ModInt a -> Word32
unModInt

-- | Returns the internal value converted to `Word32`.
--
-- ==== Complecity
-- - \(O(1)\)
--
-- @since 1.0.0.0
{-# INLINE val64 #-}
val64 :: (KnownNat a) => ModInt a -> Word64
val64 :: forall (a :: Nat). KnownNat a => ModInt a -> Word64
val64 = Word32 -> Word64
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Word32 -> Word64) -> (ModInt a -> Word32) -> ModInt a -> Word64
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ModInt a -> Word32
forall {k} (a :: k). ModInt a -> Word32
unModInt

-- | Returns \(x^n\). The implementation is a bit more efficient than `^`.
--
-- ==== Constraints
-- - \(0 \le n\)
--
-- ==== Complexity
-- - \(O(\log n)\)
--
-- @since 1.0.0.0
{-# INLINE pow #-}
pow :: forall a. (HasCallStack, KnownNat a) => ModInt a -> Int -> ModInt a
pow :: forall (a :: Nat).
(HasCallStack, KnownNat a) =>
ModInt a -> Int -> ModInt a
pow (ModInt Word32
x0) Int
n0 = Word32 -> ModInt a
forall {k} (a :: k). Word32 -> ModInt a
ModInt (Word32 -> ModInt a) -> (Word64 -> Word32) -> Word64 -> ModInt a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Word64 -> Word32
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Word64 -> ModInt a) -> Word64 -> ModInt a
forall a b. (a -> b) -> a -> b
$ Int -> Word64 -> Word64 -> Word64
inner Int
n0 Word64
1 (Word32 -> Word64
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word32
x0)
  where
    !()
_ = HasCallStack => Bool -> String -> ()
Bool -> String -> ()
ACIA.runtimeAssert (Int
0 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
n0) (String -> ()) -> String -> ()
forall a b. (a -> b) -> a -> b
$ String
"AtCoder.ModInt.pow: given negative exponential `n`: " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Int -> String
forall a. Show a => a -> String
show Int
n0 String -> ShowS
forall a. [a] -> [a] -> [a]
++ ShowS
forall a. Show a => a -> String
show String
"`"
    bt :: Barrett
bt = Word64 -> Barrett
ACIBT.new64 (Word64 -> Barrett) -> Word64 -> Barrett
forall a b. (a -> b) -> a -> b
$ Nat -> Word64
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Proxy# a -> Nat
forall (n :: Nat). KnownNat n => Proxy# n -> Nat
natVal' (forall (a :: Nat). Proxy# a
forall {k} (a :: k). Proxy# a
proxy# @a))
    inner :: Int -> Word64 -> Word64 -> Word64
    inner :: Int -> Word64 -> Word64 -> Word64
inner !Int
n !Word64
r !Word64
y
      | Int
n Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0 = Word64
r
      | Bool
otherwise =
          let r' :: Word64
r' = if Int -> Bool
forall a. Integral a => a -> Bool
odd Int
n then Barrett -> Word64 -> Word64 -> Word64
ACIBT.mulMod Barrett
bt Word64
r Word64
y else Word64
r
              y' :: Word64
y' = Barrett -> Word64 -> Word64 -> Word64
ACIBT.mulMod Barrett
bt Word64
y Word64
y
           in Int -> Word64 -> Word64 -> Word64
inner (Int
n Int -> Int -> Int
forall a. Bits a => a -> Int -> a
!>>. Int
1) Word64
r' Word64
y'

-- Original ACL version seems like slower as in the benchmark
-- pow :: (HasCallStack, KnownNat a) => ModInt a -> Int -> ModInt a
-- pow x0 n0 = inner x0 n0 1
--   where
--     !_ = ACIA.runtimeAssert (0 <= n0) $ "AtCoder.ModInt.pow: given negative exponential `n`: " ++ show n0 ++ show "`"
--     inner !x !n !r
--       | n == 0 = r
--       | otherwise =
--           let !r' = if odd n then r * x else r
--            in inner (x * x) (n !>>. 1) r'

-- | Returns \(y\) with \(xy \equiv 1\).
--
-- ==== Constraints
-- - @\gcd(val x, modulus x) == 1@.
--
-- ==== Complexity
-- - \(O(\log \mathrm{mod})\)
--
-- @since 1.0.0.0
{-# INLINE inv #-}
inv :: forall a. (HasCallStack, Modulus a) => ModInt a -> ModInt a
inv :: forall (a :: Nat).
(HasCallStack, Modulus a) =>
ModInt a -> ModInt a
inv self :: ModInt a
self@(ModInt Word32
x)
  | Proxy# a -> Bool
forall (a :: Nat). Modulus a => Proxy# a -> Bool
isPrimeModulus (forall (a :: Nat). Proxy# a
forall {k} (a :: k). Proxy# a
proxy# @a) =
      let !()
_ = HasCallStack => Bool -> String -> ()
Bool -> String -> ()
ACIA.runtimeAssert (Word32
x Word32 -> Word32 -> Bool
forall a. Eq a => a -> a -> Bool
/= Word32
0) String
"AtCoder.ModInt.inv: tried to perform zero division"
       in ModInt a -> Int -> ModInt a
forall (a :: Nat).
(HasCallStack, KnownNat a) =>
ModInt a -> Int -> ModInt a
pow ModInt a
self (Nat -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Proxy# a -> Nat
forall (n :: Nat). KnownNat n => Proxy# n -> Nat
natVal' (forall (a :: Nat). Proxy# a
forall {k} (a :: k). Proxy# a
proxy# @a)) Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
2)
  | Bool
otherwise =
      let (!Int
eg1, !Int
eg2) = Int -> Int -> (Int, Int)
ACIM.invGcd (Word32 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word32
x) (Int -> (Int, Int)) -> Int -> (Int, Int)
forall a b. (a -> b) -> a -> b
$ Nat -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Proxy# a -> Nat
forall (n :: Nat). KnownNat n => Proxy# n -> Nat
natVal' (forall (a :: Nat). Proxy# a
forall {k} (a :: k). Proxy# a
proxy# @a))
          !()
_ = HasCallStack => Bool -> String -> ()
Bool -> String -> ()
ACIA.runtimeAssert (Int
eg1 Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
1) String
"AtCoder.ModInt.inv: `x^(-1) mod m` cannot be calculated when `gcd x modulus /= 1`"
       in Int -> ModInt a
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
eg2

-- | @since 1.0.0.0
deriving newtype instance (KnownNat p) => Real (ModInt p)

-- | @since 1.0.0.0
instance (KnownNat p) => Num (ModInt p) where
  {-# INLINE (+) #-}
  (ModInt !Word32
x1) + :: ModInt p -> ModInt p -> ModInt p
+ (ModInt !Word32
x2)
    | Word32
x' Word32 -> Word32 -> Bool
forall a. Ord a => a -> a -> Bool
>= Word32
m = Word32 -> ModInt p
forall {k} (a :: k). Word32 -> ModInt a
ModInt (Word32 -> ModInt p) -> Word32 -> ModInt p
forall a b. (a -> b) -> a -> b
$! Word32
x' Word32 -> Word32 -> Word32
forall a. Num a => a -> a -> a
- Word32
m
    | Bool
otherwise = Word32 -> ModInt p
forall {k} (a :: k). Word32 -> ModInt a
ModInt Word32
x'
    where
      !x' :: Word32
x' = Word32
x1 Word32 -> Word32 -> Word32
forall a. Num a => a -> a -> a
+ Word32
x2
      !m :: Word32
m = Nat -> Word32
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Proxy# p -> Nat
forall (n :: Nat). KnownNat n => Proxy# n -> Nat
natVal' (forall (a :: Nat). Proxy# a
forall {k} (a :: k). Proxy# a
proxy# @p))
  {-# INLINE (-) #-}
  (ModInt !Word32
x1) - :: ModInt p -> ModInt p -> ModInt p
- (ModInt !Word32
x2)
    | Word32
x' Word32 -> Word32 -> Bool
forall a. Ord a => a -> a -> Bool
>= Word32
m = Word32 -> ModInt p
forall {k} (a :: k). Word32 -> ModInt a
ModInt (Word32 -> ModInt p) -> Word32 -> ModInt p
forall a b. (a -> b) -> a -> b
$! Word32
x' Word32 -> Word32 -> Word32
forall a. Num a => a -> a -> a
+ Word32
m -- loops
    | Bool
otherwise = Word32 -> ModInt p
forall {k} (a :: k). Word32 -> ModInt a
ModInt Word32
x'
    where
      !x' :: Word32
x' = Word32
x1 Word32 -> Word32 -> Word32
forall a. Num a => a -> a -> a
- Word32
x2
      !m :: Word32
m = Nat -> Word32
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Proxy# p -> Nat
forall (n :: Nat). KnownNat n => Proxy# n -> Nat
natVal' (forall (a :: Nat). Proxy# a
forall {k} (a :: k). Proxy# a
proxy# @p))
  {-# INLINE (*) #-}
  (ModInt !Word32
x1) * :: ModInt p -> ModInt p -> ModInt p
* (ModInt !Word32
x2) = Word32 -> ModInt p
forall {k} (a :: k). Word32 -> ModInt a
ModInt (Word32 -> ModInt p) -> Word32 -> ModInt p
forall a b. (a -> b) -> a -> b
$! Word64 -> Word32
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Word64
x' Word64 -> Word64 -> Word64
forall a. Integral a => a -> a -> a
`rem` Word64
m)
    where
      !Word64
x' :: Word64 = Word32 -> Word64
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word32
x1 Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
* Word32 -> Word64
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word32
x2
      !Word64
m :: Word64 = Nat -> Word64
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Proxy# p -> Nat
forall (n :: Nat). KnownNat n => Proxy# n -> Nat
natVal' (forall (a :: Nat). Proxy# a
forall {k} (a :: k). Proxy# a
proxy# @p))
  {-# INLINE negate #-}
  negate :: ModInt p -> ModInt p
negate ModInt p
x = ModInt p
0 ModInt p -> ModInt p -> ModInt p
forall a. Num a => a -> a -> a
- ModInt p
x
  {-# INLINE abs #-}
  abs :: ModInt p -> ModInt p
abs = ModInt p -> ModInt p
forall a. a -> a
id
  {-# INLINE signum #-}
  signum :: ModInt p -> ModInt p
signum ModInt p
_ = Word32 -> ModInt p
forall {k} (a :: k). Word32 -> ModInt a
ModInt Word32
1
  {-# INLINE fromInteger #-}
  fromInteger :: Integer -> ModInt p
fromInteger = Word32 -> ModInt p
forall {k} (a :: k). Word32 -> ModInt a
ModInt (Word32 -> ModInt p) -> (Integer -> Word32) -> Integer -> ModInt p
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Integer -> Word32
forall a. Num a => Integer -> a
fromInteger (Integer -> Word32) -> (Integer -> Integer) -> Integer -> Word32
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Nat -> Integer
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Proxy# p -> Nat
forall (n :: Nat). KnownNat n => Proxy# n -> Nat
natVal' (forall (a :: Nat). Proxy# a
forall {k} (a :: k). Proxy# a
proxy# @p)))

-- | @since 1.0.0.0
instance (KnownNat p) => Bounded (ModInt p) where
  {-# INLINE minBound #-}
  minBound :: ModInt p
minBound = Word32 -> ModInt p
forall {k} (a :: k). Word32 -> ModInt a
ModInt Word32
0
  {-# INLINE maxBound #-}
  maxBound :: ModInt p
maxBound = Word32 -> ModInt p
forall {k} (a :: k). Word32 -> ModInt a
ModInt (Word32 -> ModInt p) -> Word32 -> ModInt p
forall a b. (a -> b) -> a -> b
$! Nat -> Word32
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Proxy# p -> Nat
forall (n :: Nat). KnownNat n => Proxy# n -> Nat
natVal' (forall (a :: Nat). Proxy# a
forall {k} (a :: k). Proxy# a
proxy# @p)) Word32 -> Word32 -> Word32
forall a. Num a => a -> a -> a
- Word32
1

-- | @since 1.0.0.0
instance (KnownNat p) => Enum (ModInt p) where
  {-# INLINE toEnum #-}
  toEnum :: Int -> ModInt p
toEnum = Int -> ModInt p
forall (a :: Nat). KnownNat a => Int -> ModInt a
new
  {-# INLINE fromEnum #-}
  fromEnum :: ModInt p -> Int
fromEnum = Word32 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Word32 -> Int) -> (ModInt p -> Word32) -> ModInt p -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ModInt p -> Word32
forall {k} (a :: k). ModInt a -> Word32
unModInt

-- | @since 1.0.0.0
instance (Modulus p) => Integral (ModInt p) where
  {-# INLINE quotRem #-}
  quotRem :: ModInt p -> ModInt p -> (ModInt p, ModInt p)
quotRem ModInt p
x ModInt p
y = (ModInt p
x ModInt p -> ModInt p -> ModInt p
forall a. Fractional a => a -> a -> a
/ ModInt p
y, ModInt p
x ModInt p -> ModInt p -> ModInt p
forall a. Num a => a -> a -> a
- ModInt p
x ModInt p -> ModInt p -> ModInt p
forall a. Fractional a => a -> a -> a
/ ModInt p
y ModInt p -> ModInt p -> ModInt p
forall a. Num a => a -> a -> a
* ModInt p
y)
  {-# INLINE toInteger #-}
  toInteger :: ModInt p -> Integer
toInteger = (Word32 -> Integer) -> ModInt p -> Integer
forall a b. Coercible a b => a -> b
coerce (forall a. Integral a => a -> Integer
toInteger @Word32)

-- | @since 1.0.0.0
instance (Modulus p) => Fractional (ModInt p) where
  {-# INLINE recip #-}
  recip :: ModInt p -> ModInt p
recip = ModInt p -> ModInt p
forall (a :: Nat).
(HasCallStack, Modulus a) =>
ModInt a -> ModInt a
inv
  {-# INLINE fromRational #-}
  fromRational :: Rational -> ModInt p
fromRational Rational
q = Integer -> ModInt p
forall a. Num a => Integer -> a
fromInteger (Rational -> Integer
forall a. Ratio a -> a
numerator Rational
q) ModInt p -> ModInt p -> ModInt p
forall a. Fractional a => a -> a -> a
/ Integer -> ModInt p
forall a. Num a => Integer -> a
fromInteger (Rational -> Integer
forall a. Ratio a -> a
denominator Rational
q)

-- | @since 1.0.0.0
newtype instance VU.MVector s (ModInt a) = MV_ModInt (VU.MVector s Word32)

-- | @since 1.0.0.0
newtype instance VU.Vector (ModInt a) = V_ModInt (VU.Vector Word32)

-- | @since 1.0.0.0
deriving newtype instance VGM.MVector VU.MVector (ModInt a)

-- | @since 1.0.0.0
deriving newtype instance VG.Vector VU.Vector (ModInt a)

-- | @since 1.0.0.0
instance VU.Unbox (ModInt a)