{-# LANGUAGE DataKinds #-}
{-# LANGUAGE DerivingStrategies #-}
{-# LANGUAGE MagicHash #-}
{-# LANGUAGE TypeFamilies #-}

-- | @ModInt@ for 64 bit modulus values.
--
-- @since 1.2.6.0
module AtCoder.Extra.ModInt64
  ( -- * ModInt64
    ModInt64 (..),

    -- * Constructors

    -- ** Safe constructors
    new,
    new64,

    -- ** Unsafe constructor
    unsafeNew,

    -- * Accessors

    -- ** Modulus value
    modulus,

    -- ** Internal value
    val,
    val64,

    -- * Operators
    pow,
    inv,
  )
where

import AtCoder.Internal.Assert qualified as ACIA
import AtCoder.Extra.Math.Montgomery64 qualified as M64
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 (Word64)
import GHC.Exts (proxy#)
import GHC.Stack (HasCallStack)
import GHC.TypeNats (KnownNat, natVal')

-- | `Word64` value that treats the modular arithmetic.
--
-- @since 1.2.6.0
newtype ModInt64 a = ModInt64
  { -- | Montgomery form of the value. Use `val` to retrieve the value.
    --
    -- @since 1.2.6.0
    forall {k} (a :: k). ModInt64 a -> Word64
unModInt64 :: Word64
  }
  deriving
    ( -- | @since 1.2.6.0
      Addr# -> Int# -> ModInt64 a
ByteArray# -> Int# -> ModInt64 a
Proxy (ModInt64 a) -> Int#
ModInt64 a -> Int#
(Proxy (ModInt64 a) -> Int#)
-> (ModInt64 a -> Int#)
-> (Proxy (ModInt64 a) -> Int#)
-> (ModInt64 a -> Int#)
-> (ByteArray# -> Int# -> ModInt64 a)
-> (forall s.
    MutableByteArray# s
    -> Int# -> State# s -> (# State# s, ModInt64 a #))
-> (forall s.
    MutableByteArray# s -> Int# -> ModInt64 a -> State# s -> State# s)
-> (forall s.
    MutableByteArray# s
    -> Int# -> Int# -> ModInt64 a -> State# s -> State# s)
-> (Addr# -> Int# -> ModInt64 a)
-> (forall s.
    Addr# -> Int# -> State# s -> (# State# s, ModInt64 a #))
-> (forall s. Addr# -> Int# -> ModInt64 a -> State# s -> State# s)
-> (forall s.
    Addr# -> Int# -> Int# -> ModInt64 a -> State# s -> State# s)
-> Prim (ModInt64 a)
forall s.
Addr# -> Int# -> Int# -> ModInt64 a -> State# s -> State# s
forall s. Addr# -> Int# -> State# s -> (# State# s, ModInt64 a #)
forall s. Addr# -> Int# -> ModInt64 a -> State# s -> State# s
forall s.
MutableByteArray# s
-> Int# -> Int# -> ModInt64 a -> State# s -> State# s
forall s.
MutableByteArray# s
-> Int# -> State# s -> (# State# s, ModInt64 a #)
forall s.
MutableByteArray# s -> Int# -> ModInt64 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# -> ModInt64 a
forall k (a :: k). ByteArray# -> Int# -> ModInt64 a
forall k (a :: k). Proxy (ModInt64 a) -> Int#
forall k (a :: k). ModInt64 a -> Int#
forall k (a :: k) s.
Addr# -> Int# -> Int# -> ModInt64 a -> State# s -> State# s
forall k (a :: k) s.
Addr# -> Int# -> State# s -> (# State# s, ModInt64 a #)
forall k (a :: k) s.
Addr# -> Int# -> ModInt64 a -> State# s -> State# s
forall k (a :: k) s.
MutableByteArray# s
-> Int# -> Int# -> ModInt64 a -> State# s -> State# s
forall k (a :: k) s.
MutableByteArray# s
-> Int# -> State# s -> (# State# s, ModInt64 a #)
forall k (a :: k) s.
MutableByteArray# s -> Int# -> ModInt64 a -> State# s -> State# s
$csizeOfType# :: forall k (a :: k). Proxy (ModInt64 a) -> Int#
sizeOfType# :: Proxy (ModInt64 a) -> Int#
$csizeOf# :: forall k (a :: k). ModInt64 a -> Int#
sizeOf# :: ModInt64 a -> Int#
$calignmentOfType# :: forall k (a :: k). Proxy (ModInt64 a) -> Int#
alignmentOfType# :: Proxy (ModInt64 a) -> Int#
$calignment# :: forall k (a :: k). ModInt64 a -> Int#
alignment# :: ModInt64 a -> Int#
$cindexByteArray# :: forall k (a :: k). ByteArray# -> Int# -> ModInt64 a
indexByteArray# :: ByteArray# -> Int# -> ModInt64 a
$creadByteArray# :: forall k (a :: k) s.
MutableByteArray# s
-> Int# -> State# s -> (# State# s, ModInt64 a #)
readByteArray# :: forall s.
MutableByteArray# s
-> Int# -> State# s -> (# State# s, ModInt64 a #)
$cwriteByteArray# :: forall k (a :: k) s.
MutableByteArray# s -> Int# -> ModInt64 a -> State# s -> State# s
writeByteArray# :: forall s.
MutableByteArray# s -> Int# -> ModInt64 a -> State# s -> State# s
$csetByteArray# :: forall k (a :: k) s.
MutableByteArray# s
-> Int# -> Int# -> ModInt64 a -> State# s -> State# s
setByteArray# :: forall s.
MutableByteArray# s
-> Int# -> Int# -> ModInt64 a -> State# s -> State# s
$cindexOffAddr# :: forall k (a :: k). Addr# -> Int# -> ModInt64 a
indexOffAddr# :: Addr# -> Int# -> ModInt64 a
$creadOffAddr# :: forall k (a :: k) s.
Addr# -> Int# -> State# s -> (# State# s, ModInt64 a #)
readOffAddr# :: forall s. Addr# -> Int# -> State# s -> (# State# s, ModInt64 a #)
$cwriteOffAddr# :: forall k (a :: k) s.
Addr# -> Int# -> ModInt64 a -> State# s -> State# s
writeOffAddr# :: forall s. Addr# -> Int# -> ModInt64 a -> State# s -> State# s
$csetOffAddr# :: forall k (a :: k) s.
Addr# -> Int# -> Int# -> ModInt64 a -> State# s -> State# s
setOffAddr# :: forall s.
Addr# -> Int# -> Int# -> ModInt64 a -> State# s -> State# s
P.Prim
    )

-- | @since 1.2.6.0
instance (KnownNat a) => Eq (ModInt64 a) where
  {-# INLINE (==) #-}
  ModInt64 Word64
x == :: ModInt64 a -> ModInt64 a -> Bool
== ModInt64 Word64
y = Word64 -> Word64 -> Word64 -> Bool
M64.eq (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))) Word64
x Word64
y

-- | @since 1.2.6.0
instance (KnownNat a) => Ord (ModInt64 a) where
  {-# INLINE compare #-}
  compare :: ModInt64 a -> ModInt64 a -> Ordering
compare (ModInt64 Word64
a) (ModInt64 Word64
b) = Word64 -> Word64 -> Ordering
forall a. Ord a => a -> a -> Ordering
compare Word64
a Word64
b

-- | @since 1.2.6.0
instance (KnownNat a) => Read (ModInt64 a) where
  {-# INLINE readsPrec #-}
  readsPrec :: Int -> ReadS (ModInt64 a)
readsPrec Int
p String
s = [(Integer -> ModInt64 a
forall a. Num a => Integer -> a
fromInteger Integer
x, String
r) | (!Integer
x, !String
r) <- Int -> ReadS Integer
forall a. Read a => Int -> ReadS a
readsPrec Int
p String
s]

-- | @since 1.2.6.0
instance (KnownNat a) => Show (ModInt64 a) where
  {-# INLINE show #-}
  show :: ModInt64 a -> String
show = Int -> String
forall a. Show a => a -> String
show (Int -> String) -> (ModInt64 a -> Int) -> ModInt64 a -> String
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ModInt64 a -> Int
forall (a :: Nat). KnownNat a => ModInt64 a -> Int
val

-- | \(O(1)\) Creates a `ModInt64` from an `Int` value taking the mod.
--
-- @since 1.2.6.0
{-# INLINE new #-}
new :: forall a. (KnownNat a) => Int -> ModInt64 a
new :: forall (a :: Nat). KnownNat a => Int -> ModInt64 a
new = Word64 -> ModInt64 a
forall {k} (a :: k). Word64 -> ModInt64 a
ModInt64 (Word64 -> ModInt64 a) -> (Int -> Word64) -> Int -> ModInt64 a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Montgomery64 -> Word64 -> Word64
M64.encode (Proxy# a -> Montgomery64
forall (a :: Nat). KnownNat a => Proxy# a -> Montgomery64
M64.new (forall (a :: Nat). Proxy# a
forall {k} (a :: k). Proxy# a
proxy# @a)) (Word64 -> Word64) -> (Int -> Word64) -> Int -> Word64
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Word64
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int -> Word64) -> (Int -> Int) -> Int -> Word64
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` Int
m)
  where
    !m :: Int
m = 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' (forall (a :: Nat). Proxy# a
forall {k} (a :: k). Proxy# a
proxy# @a)

-- | \(O(1)\) Creates a `ModInt64` from a `Word64` value taking the mod.
--
-- @since 1.2.6.0
{-# INLINE new64 #-}
new64 :: forall a. (KnownNat a) => Word64 -> ModInt64 a
new64 :: forall (a :: Nat). KnownNat a => Word64 -> ModInt64 a
new64 = Word64 -> ModInt64 a
forall {k} (a :: k). Word64 -> ModInt64 a
ModInt64 (Word64 -> ModInt64 a)
-> (Word64 -> Word64) -> Word64 -> ModInt64 a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Montgomery64 -> Word64 -> Word64
M64.encode (Proxy# a -> Montgomery64
forall (a :: Nat). KnownNat a => Proxy# a -> Montgomery64
M64.new (forall (a :: Nat). Proxy# a
forall {k} (a :: k). Proxy# a
proxy# @a))

-- | \(O(1)\) Creates `ModInt64` from a Montgomery form with no validation.
--
-- @since 1.2.6.0
{-# INLINE unsafeNew #-}
unsafeNew :: (KnownNat a) => Word64 -> ModInt64 a
unsafeNew :: forall (a :: Nat). KnownNat a => Word64 -> ModInt64 a
unsafeNew = Word64 -> ModInt64 a
forall {k} (a :: k). Word64 -> ModInt64 a
ModInt64

-- | \(O(1)\) Retrieve the mod from a `ModInt64` object.
--
-- ==== Complecity
-- - \(O(1)\)
--
-- @since 1.2.6.0
{-# INLINE modulus #-}
modulus :: forall a. (KnownNat a) => ModInt64 a -> Int
modulus :: forall (a :: Nat). KnownNat a => ModInt64 a -> Int
modulus ModInt64 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))

-- | \(O(1)\) Returns the internal value in `Int`.
--
-- ==== Complecity
-- - \(O(1)\)
--
-- @since 1.2.6.0
{-# INLINE val #-}
val :: forall a. (KnownNat a) => ModInt64 a -> Int
val :: forall (a :: Nat). KnownNat a => ModInt64 a -> Int
val = Word64 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Word64 -> Int) -> (ModInt64 a -> Word64) -> ModInt64 a -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ModInt64 a -> Word64
forall (a :: Nat). KnownNat a => ModInt64 a -> Word64
val64

-- | \(O(1)\) Returns the internal value in `Word64`.
--
-- ==== Complecity
-- - \(O(1)\)
--
-- @since 1.2.6.0
{-# INLINE val64 #-}
val64 :: forall a. (KnownNat a) => ModInt64 a -> Word64
val64 :: forall (a :: Nat). KnownNat a => ModInt64 a -> Word64
val64 (ModInt64 Word64
x) = Montgomery64 -> Word64 -> Word64
M64.decode (Proxy# a -> Montgomery64
forall (a :: Nat). KnownNat a => Proxy# a -> Montgomery64
M64.new (forall (a :: Nat). Proxy# a
forall {k} (a :: k). Proxy# a
proxy# @a)) Word64
x

-- | \(O(\log n\) Returns \(x^n\). The implementation is a bit more efficient than `^`.
--
-- ==== Constraints
-- - \(0 \le n\)
--
-- @since 1.2.6.0
{-# INLINE pow #-}
pow :: forall a. (HasCallStack, KnownNat a) => ModInt64 a -> Int -> ModInt64 a
pow :: forall (a :: Nat).
(HasCallStack, KnownNat a) =>
ModInt64 a -> Int -> ModInt64 a
pow (ModInt64 Word64
x) Int
n = Word64 -> ModInt64 a
forall {k} (a :: k). Word64 -> ModInt64 a
ModInt64 (Word64 -> ModInt64 a) -> Word64 -> ModInt64 a
forall a b. (a -> b) -> a -> b
$! HasCallStack => Montgomery64 -> Word64 -> Int -> Word64
Montgomery64 -> Word64 -> Int -> Word64
M64.powMod (Proxy# a -> Montgomery64
forall (a :: Nat). KnownNat a => Proxy# a -> Montgomery64
M64.new (forall (a :: Nat). Proxy# a
forall {k} (a :: k). Proxy# a
proxy# @a)) Word64
x Int
n

-- TODO: move invMod to Montgomery64
-- TODO: time complexity of `inv`?

-- | Returns \(y\) such that \(xy \equiv 1\) holds.
--
-- ==== Constraints
-- - The value must not be zero.
--
-- @since 1.2.6.0
{-# INLINE inv #-}
inv :: forall a. (HasCallStack, KnownNat a) => ModInt64 a -> ModInt64 a
-- TODO: assert zero division?
inv :: forall (a :: Nat).
(HasCallStack, KnownNat a) =>
ModInt64 a -> ModInt64 a
inv ModInt64 a
self = Int -> Int -> Int -> Int -> ModInt64 a
forall {a :: Nat}.
KnownNat a =>
Int -> Int -> Int -> Int -> ModInt64 a
inner (ModInt64 a -> Int
forall (a :: Nat). KnownNat a => ModInt64 a -> Int
val ModInt64 a
self) Int
m Int
1 Int
0
  where
    !()
_ = HasCallStack => Bool -> String -> ()
Bool -> String -> ()
ACIA.runtimeAssert (ModInt64 a -> Int
forall (a :: Nat). KnownNat a => ModInt64 a -> Int
val ModInt64 a
self Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
/= Int
0) String
"AtCoder.Extra.ModInt64.inv: given zero"
    !m :: Int
m = 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))
    inner :: Int -> Int -> Int -> Int -> ModInt64 a
inner Int
x Int
y Int
u Int
v
      | Int
y Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
0 = Int -> ModInt64 a
forall (a :: Nat). KnownNat a => Int -> ModInt64 a
new Int
u
      | Bool
otherwise = Int -> Int -> Int -> Int -> ModInt64 a
inner Int
x' Int
y' Int
u' Int
v'
      where
        x' :: Int
x' = Int
y
        y' :: Int
y' = Int
x Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
t Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
y
        u' :: Int
u' = Int
v
        v' :: Int
v' = Int
u Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
t Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
v
        t :: Int
t = Int
x Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
y

-- https://github.com/NyaanNyaan/library/blob/master/modint/montgomery-modint.hpp
-- constexpr mint inverse() const {
--   int x = get(), y = mod, u = 1, v = 0, t = 0, tmp = 0;
--   while (y > 0) {
--     t = x / y;
--     x -= t * y, u -= t * v;
--     tmp = x, x = y, y = tmp;
--     tmp = u, u = v, v = tmp;
--   }
--   return mint{u};
-- }

-- | @since 1.2.6.0
deriving newtype instance (KnownNat p) => Real (ModInt64 p)

-- | @since 1.2.6.0
instance forall p. (KnownNat p) => Num (ModInt64 p) where
  {-# INLINE (+) #-}
  (ModInt64 !Word64
x1) + :: ModInt64 p -> ModInt64 p -> ModInt64 p
+ (ModInt64 !Word64
x2) = Word64 -> ModInt64 p
forall {k} (a :: k). Word64 -> ModInt64 a
ModInt64 (Word64 -> ModInt64 p) -> Word64 -> ModInt64 p
forall a b. (a -> b) -> a -> b
$! Word64 -> Word64 -> Word64 -> Word64
M64.addMod Word64
m Word64
x1 Word64
x2
    where
      !m :: Word64
m = 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 (-) #-}
  (ModInt64 !Word64
x1) - :: ModInt64 p -> ModInt64 p -> ModInt64 p
- (ModInt64 !Word64
x2) = Word64 -> ModInt64 p
forall {k} (a :: k). Word64 -> ModInt64 a
ModInt64 (Word64 -> ModInt64 p) -> Word64 -> ModInt64 p
forall a b. (a -> b) -> a -> b
$! Word64 -> Word64 -> Word64 -> Word64
M64.subMod Word64
m Word64
x1 Word64
x2
    where
      !m :: Word64
m = 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 (*) #-}
  (ModInt64 !Word64
x1) * :: ModInt64 p -> ModInt64 p -> ModInt64 p
* (ModInt64 !Word64
x2) = Word64 -> ModInt64 p
forall {k} (a :: k). Word64 -> ModInt64 a
ModInt64 (Word64 -> ModInt64 p) -> Word64 -> ModInt64 p
forall a b. (a -> b) -> a -> b
$! Montgomery64 -> Word64 -> Word64 -> Word64
M64.mulMod (Proxy# p -> Montgomery64
forall (a :: Nat). KnownNat a => Proxy# a -> Montgomery64
M64.new (forall (a :: Nat). Proxy# a
forall {k} (a :: k). Proxy# a
proxy# @p)) Word64
x1 Word64
x2
  {-# INLINE negate #-}
  negate :: ModInt64 p -> ModInt64 p
negate ModInt64 p
x = ModInt64 p
0 ModInt64 p -> ModInt64 p -> ModInt64 p
forall a. Num a => a -> a -> a
- ModInt64 p
x
  {-# INLINE abs #-}
  abs :: ModInt64 p -> ModInt64 p
abs = ModInt64 p -> ModInt64 p
forall a. a -> a
id
  {-# INLINE signum #-}
  signum :: ModInt64 p -> ModInt64 p
signum ModInt64 p
_ = Word64 -> ModInt64 p
forall {k} (a :: k). Word64 -> ModInt64 a
ModInt64 (Word64 -> ModInt64 p) -> Word64 -> ModInt64 p
forall a b. (a -> b) -> a -> b
$ Montgomery64 -> Word64 -> Word64
M64.encode (Proxy# p -> Montgomery64
forall (a :: Nat). KnownNat a => Proxy# a -> Montgomery64
M64.new (forall (a :: Nat). Proxy# a
forall {k} (a :: k). Proxy# a
proxy# @p)) Word64
1
  -- because the input value can be negative, be sure to take the mod:
  {-# INLINE fromInteger #-}
  fromInteger :: Integer -> ModInt64 p
fromInteger = Word64 -> ModInt64 p
forall {k} (a :: k). Word64 -> ModInt64 a
ModInt64 (Word64 -> ModInt64 p)
-> (Integer -> Word64) -> Integer -> ModInt64 p
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Montgomery64 -> Word64 -> Word64
M64.encode (Proxy# p -> Montgomery64
forall (a :: Nat). KnownNat a => Proxy# a -> Montgomery64
M64.new (forall (a :: Nat). Proxy# a
forall {k} (a :: k). Proxy# a
proxy# @p)) (Word64 -> Word64) -> (Integer -> Word64) -> Integer -> Word64
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Integer -> Word64
forall a. Num a => Integer -> a
fromInteger (Integer -> Word64) -> (Integer -> Integer) -> Integer -> Word64
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
m)
    where
      !m :: Integer
m = Nat -> Integer
forall a. Integral a => a -> Integer
toInteger (Nat -> Integer) -> Nat -> Integer
forall a b. (a -> b) -> a -> b
$ 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.2.6.0
instance (KnownNat p) => Bounded (ModInt64 p) where
  {-# INLINE minBound #-}
  minBound :: ModInt64 p
minBound = Word64 -> ModInt64 p
forall {k} (a :: k). Word64 -> ModInt64 a
ModInt64 Word64
0
  {-# INLINE maxBound #-}
  maxBound :: ModInt64 p
maxBound = Word64 -> ModInt64 p
forall {k} (a :: k). Word64 -> ModInt64 a
ModInt64 (Word64 -> ModInt64 p)
-> (Word64 -> Word64) -> Word64 -> ModInt64 p
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Montgomery64 -> Word64 -> Word64
M64.encode (Proxy# p -> Montgomery64
forall (a :: Nat). KnownNat a => Proxy# a -> Montgomery64
M64.new (forall (a :: Nat). Proxy# a
forall {k} (a :: k). Proxy# a
proxy# @p)) (Word64 -> ModInt64 p) -> Word64 -> ModInt64 p
forall a b. (a -> b) -> a -> b
$! 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)) Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
- Word64
1

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

-- | @since 1.2.6.0
instance (KnownNat p) => Integral (ModInt64 p) where
  -- FIXME: THIS IS COMPLETELY WRONG. Compare with `ModInt`.
  {-# INLINE quotRem #-}
  -- quotRem x y =
  --   let !x' = val x
  --       !y' = val y
  --       (!q, !r) = x' `quotRem` y'
  --    in (new q, new r)
  quotRem :: ModInt64 p -> ModInt64 p -> (ModInt64 p, ModInt64 p)
quotRem ModInt64 p
x ModInt64 p
y = (ModInt64 p
x ModInt64 p -> ModInt64 p -> ModInt64 p
forall a. Fractional a => a -> a -> a
/ ModInt64 p
y, ModInt64 p
x ModInt64 p -> ModInt64 p -> ModInt64 p
forall a. Num a => a -> a -> a
- ModInt64 p
x ModInt64 p -> ModInt64 p -> ModInt64 p
forall a. Fractional a => a -> a -> a
/ ModInt64 p
y ModInt64 p -> ModInt64 p -> ModInt64 p
forall a. Num a => a -> a -> a
* ModInt64 p
y)
  {-# INLINE toInteger #-}
  toInteger :: ModInt64 p -> Integer
toInteger = Int -> Integer
forall a. Integral a => a -> Integer
toInteger (Int -> Integer) -> (ModInt64 p -> Int) -> ModInt64 p -> Integer
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ModInt64 p -> Int
forall (a :: Nat). KnownNat a => ModInt64 a -> Int
val

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

-- | @since 1.2.6.0
newtype instance VU.MVector s (ModInt64 a) = MV_ModInt64 (VU.MVector s Word64)

-- | @since 1.2.6.0
newtype instance VU.Vector (ModInt64 a) = V_ModInt64 (VU.Vector Word64)

-- | @since 1.2.6.0
deriving newtype instance VGM.MVector VU.MVector (ModInt64 a)

-- | @since 1.2.6.0
deriving newtype instance VG.Vector VU.Vector (ModInt64 a)

-- | @since 1.2.6.0
instance VU.Unbox (ModInt64 a)