    -- |
    -- Module:      Data.Mod
    -- Copyright:   (c) 2017-2022 Andrew Lelechenko
    -- Licence:     MIT
    -- Maintainer:  Andrew Lelechenko <andrew.lelechenko@gmail.com>
    --
    -- <https://en.wikipedia.org/wiki/Modular_arithmetic Modular arithmetic>,
    -- promoting moduli to the type level, with an emphasis on performance.
    -- Originally part of the <https://hackage.haskell.org/package/arithmoi arithmoi> package.
    --
    -- This module supports moduli of arbitrary size.
    -- Use "Data.Mod.Word" to achieve better performance,
    -- when your moduli fit into 'Word'.

    {-# LANGUAGE BangPatterns          #-}
    {-# LANGUAGE CPP                   #-}
    {-# LANGUAGE DataKinds             #-}
    {-# LANGUAGE DeriveGeneric         #-}
    {-# LANGUAGE MagicHash             #-}
    {-# LANGUAGE MultiParamTypeClasses #-}
    {-# LANGUAGE ScopedTypeVariables   #-}
    {-# LANGUAGE TypeApplications      #-}
    {-# LANGUAGE TypeFamilies          #-}
    {-# LANGUAGE UnboxedTuples         #-}

    module Data.Mod
      ( Mod
      , unMod
      , invertMod
      , (^%)
      ) where

    import Control.Exception
    import Control.DeepSeq
    import Control.Monad
    import Data.Bits
    import Data.Mod.Compat (timesWord2#, remWord2#)
    import Data.Ratio
    import Data.Word (Word8)
    #ifdef MIN_VERSION_semirings
    import Data.Euclidean (GcdDomain(..), Euclidean(..), Field)
    import Data.Semiring (Semiring(..), Ring(..))
    #endif
    #ifdef MIN_VERSION_vector
    import Control.Monad.Primitive
    import Control.Monad.ST
    import qualified Data.Primitive.Types        as P
    import qualified Data.Vector.Generic         as G
    import qualified Data.Vector.Generic.Mutable as M
    import qualified Data.Vector.Unboxed         as U
    import qualified Data.Vector.Primitive       as P
    import Foreign (copyBytes)
    #endif
    import Foreign.Storable (Storable(..))
    import GHC.Exts hiding (timesWord2#, quotRemWord2#)
    import GHC.Generics
    import GHC.IO (IO(..))
    import GHC.Natural (Natural(..), powModNatural)
    import GHC.Num.BigNat
    import GHC.Num.Integer
    import GHC.TypeNats (Nat, KnownNat, natVal, natVal')
    import Text.Read (Read(readPrec))

    -- | This data type represents
    -- <https://en.wikipedia.org/wiki/Modular_arithmetic#Integers_modulo_n integers modulo m>,
    -- equipped with useful instances.
    --
    -- For example, 3 :: 'Mod' 10 stands for the class of integers
    -- congruent to \( 3 \bmod 10 \colon \ldots {−17}, −7, 3, 13, 23 \ldots \)
    --
    -- >>> :set -XDataKinds
    -- >>> 3 + 8 :: Mod 10 -- 3 + 8 = 11 ≡ 1 (mod 10)
    -- 1
    --
    -- __Note:__ 'Mod' 0 has no inhabitants, eventhough \( \mathbb{Z}/0\mathbb{Z} \) is technically isomorphic to \( \mathbb{Z} \).
    newtype Mod (m :: Nat) = Mod
      { forall (m :: Natural). Mod m -> Natural
    unMod :: Natural
      -- ^ The canonical representative of the residue class,
      -- always between 0 and \( m - 1 \) (inclusively).
      --
      -- >>> :set -XDataKinds
      -- >>> -1 :: Mod 10
      -- 9
      }
      deriving (Mod m -> Mod m -> Bool
    (Mod m -> Mod m -> Bool) -> (Mod m -> Mod m -> Bool) -> Eq (Mod m)
    forall (m :: Natural). Mod m -> Mod m -> Bool
    forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
    $c== :: forall (m :: Natural). Mod m -> Mod m -> Bool
    == :: Mod m -> Mod m -> Bool
    $c/= :: forall (m :: Natural). Mod m -> Mod m -> Bool
    /= :: Mod m -> Mod m -> Bool
    Eq, Eq (Mod m)
    Eq (Mod m) =>
    (Mod m -> Mod m -> Ordering)
    -> (Mod m -> Mod m -> Bool)
    -> (Mod m -> Mod m -> Bool)
    -> (Mod m -> Mod m -> Bool)
    -> (Mod m -> Mod m -> Bool)
    -> (Mod m -> Mod m -> Mod m)
    -> (Mod m -> Mod m -> Mod m)
    -> Ord (Mod m)
    Mod m -> Mod m -> Bool
    Mod m -> Mod m -> Ordering
    Mod m -> Mod m -> Mod m
    forall (m :: Natural). Eq (Mod m)
    forall (m :: Natural). Mod m -> Mod m -> Bool
    forall (m :: Natural). Mod m -> Mod m -> Ordering
    forall (m :: Natural). Mod m -> Mod m -> Mod m
    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 :: forall (m :: Natural). Mod m -> Mod m -> Ordering
    compare :: Mod m -> Mod m -> Ordering
    $c< :: forall (m :: Natural). Mod m -> Mod m -> Bool
    < :: Mod m -> Mod m -> Bool
    $c<= :: forall (m :: Natural). Mod m -> Mod m -> Bool
    <= :: Mod m -> Mod m -> Bool
    $c> :: forall (m :: Natural). Mod m -> Mod m -> Bool
    > :: Mod m -> Mod m -> Bool
    $c>= :: forall (m :: Natural). Mod m -> Mod m -> Bool
    >= :: Mod m -> Mod m -> Bool
    $cmax :: forall (m :: Natural). Mod m -> Mod m -> Mod m
    max :: Mod m -> Mod m -> Mod m
    $cmin :: forall (m :: Natural). Mod m -> Mod m -> Mod m
    min :: Mod m -> Mod m -> Mod m
    Ord, (forall x. Mod m -> Rep (Mod m) x)
    -> (forall x. Rep (Mod m) x -> Mod m) -> Generic (Mod m)
    forall (m :: Natural) x. Rep (Mod m) x -> Mod m
    forall (m :: Natural) x. Mod m -> Rep (Mod m) x
    forall x. Rep (Mod m) x -> Mod m
    forall x. Mod m -> Rep (Mod m) x
    forall a.
    (forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
    $cfrom :: forall (m :: Natural) x. Mod m -> Rep (Mod m) x
    from :: forall x. Mod m -> Rep (Mod m) x
    $cto :: forall (m :: Natural) x. Rep (Mod m) x -> Mod m
    to :: forall x. Rep (Mod m) x -> Mod m
    Generic)

    instance NFData (Mod m)

    instance Show (Mod m) where
      show :: Mod m -> String
    show (Mod Natural
    x) = Natural -> String
    forall a. Show a => a -> String
    show Natural
    x

    -- | Wrapping behaviour, similar to
    -- the existing @instance@ 'Read' 'Int'.
    instance KnownNat m => Read (Mod m) where
      readPrec :: ReadPrec (Mod m)
    readPrec = Integer -> Mod m
    forall a. Num a => Integer -> a
    fromInteger (Integer -> Mod m) -> ReadPrec Integer -> ReadPrec (Mod m)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> ReadPrec Integer
    forall a. Read a => ReadPrec a
    readPrec

    instance KnownNat m => Real (Mod m) where
      toRational :: Mod m -> Rational
    toRational (Mod Natural
    x) = Natural -> Rational
    forall a. Real a => a -> Rational
    toRational Natural
    x

    instance KnownNat m => Enum (Mod m) where
      succ :: Mod m -> Mod m
    succ Mod m
    x = if Mod m
    x Mod m -> Mod m -> Bool
    forall a. Eq a => a -> a -> Bool
    == Mod m
    forall a. Bounded a => a
    maxBound then ArithException -> Mod m
    forall a e. Exception e => e -> a
    throw ArithException
    Overflow  else (Natural -> Natural) -> Mod m -> Mod m
    forall a b. Coercible a b => a -> b
    coerce (forall a. Enum a => a -> a
    succ @Natural) Mod m
    x
      pred :: Mod m -> Mod m
    pred Mod m
    x = if Mod m
    x Mod m -> Mod m -> Bool
    forall a. Eq a => a -> a -> Bool
    == Mod m
    forall a. Bounded a => a
    minBound then ArithException -> Mod m
    forall a e. Exception e => e -> a
    throw ArithException
    Underflow else (Natural -> Natural) -> Mod m -> Mod m
    forall a b. Coercible a b => a -> b
    coerce (forall a. Enum a => a -> a
    pred @Natural) Mod m
    x

      toEnum :: Int -> Mod m
    toEnum   = Int -> Mod m
    forall a b. (Integral a, Num b) => a -> b
    fromIntegral :: Int -> Mod m
      fromEnum :: Mod m -> Int
    fromEnum = (Natural -> Int
    forall a b. (Integral a, Num b) => a -> b
    fromIntegral :: Natural -> Int) (Natural -> Int) -> (Mod m -> Natural) -> Mod m -> Int
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Mod m -> Natural
    forall (m :: Natural). Mod m -> Natural
    unMod

      enumFrom :: Mod m -> [Mod m]
    enumFrom Mod m
    x       = Mod m -> Mod m -> [Mod m]
    forall a. Enum a => a -> a -> [a]
    enumFromTo Mod m
    x Mod m
    forall a. Bounded a => a
    maxBound
      enumFromThen :: Mod m -> Mod m -> [Mod m]
    enumFromThen Mod m
    x Mod m
    y = Mod m -> Mod m -> Mod m -> [Mod m]
    forall a. Enum a => a -> a -> a -> [a]
    enumFromThenTo Mod m
    x Mod m
    y (if Mod m
    y Mod m -> Mod m -> Bool
    forall a. Ord a => a -> a -> Bool
    >= Mod m
    x then Mod m
    forall a. Bounded a => a
    maxBound else Mod m
    forall a. Bounded a => a
    minBound)

      enumFromTo :: Mod m -> Mod m -> [Mod m]
    enumFromTo     = (Natural -> Natural -> [Natural]) -> Mod m -> Mod m -> [Mod m]
    forall a b. Coercible a b => a -> b
    coerce (forall a. Enum a => a -> a -> [a]
    enumFromTo     @Natural)
      enumFromThenTo :: Mod m -> Mod m -> Mod m -> [Mod m]
    enumFromThenTo = (Natural -> Natural -> Natural -> [Natural])
    -> Mod m -> Mod m -> Mod m -> [Mod m]
    forall a b. Coercible a b => a -> b
    coerce (forall a. Enum a => a -> a -> a -> [a]
    enumFromThenTo @Natural)

    instance KnownNat m => Bounded (Mod m) where
      minBound :: Mod m
    minBound = Mod m
    mx
        where
          mx :: Mod m
    mx = if Mod m -> Natural
    forall (n :: Natural) (proxy :: Natural -> *).
    KnownNat n =>
    proxy n -> Natural
    natVal Mod m
    mx Natural -> Natural -> Bool
    forall a. Ord a => a -> a -> Bool
    > Natural
    0 then Natural -> Mod m
    forall (m :: Natural). Natural -> Mod m
    Mod Natural
    0 else ArithException -> Mod m
    forall a e. Exception e => e -> a
    throw ArithException
    DivideByZero
      maxBound :: Mod m
    maxBound = Mod m
    mx
        where
          mx :: Mod m
    mx = if Natural
    m Natural -> Natural -> Bool
    forall a. Ord a => a -> a -> Bool
    > Natural
    0 then Natural -> Mod m
    forall (m :: Natural). Natural -> Mod m
    Mod (Natural
    m Natural -> Natural -> Natural
    forall a. Num a => a -> a -> a
    - Natural
    1) else ArithException -> Mod m
    forall a e. Exception e => e -> a
    throw ArithException
    DivideByZero
          m :: Natural
    m = Mod m -> Natural
    forall (n :: Natural) (proxy :: Natural -> *).
    KnownNat n =>
    proxy n -> Natural
    natVal Mod m
    mx

    bigNatToNat :: BigNat# -> Natural
    bigNatToNat :: BigNat# -> Natural
    bigNatToNat BigNat#
    r# =
      if Int# -> Bool
    isTrue# (BigNat# -> Int#
    bigNatSize# BigNat#
    r# Int# -> Int# -> Int#
    <=# Int#
    1#) then Word# -> Natural
    NatS# (BigNat# -> Word#
    bigNatToWord# BigNat#
    r#) else BigNat -> Natural
    NatJ# (BigNat# -> BigNat
    BN# BigNat#
    r#)

    subIfGe :: BigNat# -> BigNat# -> Natural
    subIfGe :: BigNat# -> BigNat# -> Natural
    subIfGe BigNat#
    z# BigNat#
    m# = case BigNat#
    z# BigNat# -> BigNat# -> (# (# #) | BigNat# #)
    `bigNatSub` BigNat#
    m# of
      (# (# #) | #) -> BigNat -> Natural
    NatJ# (BigNat# -> BigNat
    BN# BigNat#
    z#)
      (# | BigNat#
    zm# #)   -> BigNat# -> Natural
    bigNatToNat BigNat#
    zm#

    addMod :: Natural -> Natural -> Natural -> Natural
    addMod :: Natural -> Natural -> Natural -> Natural
    addMod (NatS# Word#
    m#) (NatS# Word#
    x#) (NatS# Word#
    y#) =
      if Int# -> Bool
    isTrue# Int#
    c# Bool -> Bool -> Bool
    || Int# -> Bool
    isTrue# (Word#
    z# Word# -> Word# -> Int#
    `geWord#` Word#
    m#) then Word# -> Natural
    NatS# (Word#
    z# Word# -> Word# -> Word#
    `minusWord#` Word#
    m#) else Word# -> Natural
    NatS# Word#
    z#
      where
        !(# Word#
    z#, Int#
    c# #) = Word#
    x# Word# -> Word# -> (# Word#, Int# #)
    `addWordC#` Word#
    y#
    addMod NatS#{} Natural
    _ Natural
    _ = Natural
    forall a. a
    brokenInvariant
    addMod (NatJ# (BN# BigNat#
    m#)) (NatS# Word#
    x#) (NatS# Word#
    y#) =
      if Int# -> Bool
    isTrue# Int#
    c# then BigNat# -> BigNat# -> Natural
    subIfGe (Word# -> Word# -> BigNat#
    bigNatFromWord2# Word#
    1## Word#
    z#) BigNat#
    m# else Word# -> Natural
    NatS# Word#
    z#
      where
        !(# Word#
    z#, Int#
    c# #) = Word#
    x# Word# -> Word# -> (# Word#, Int# #)
    `addWordC#` Word#
    y#
    addMod (NatJ# (BN# BigNat#
    m#)) (NatS# Word#
    x#) (NatJ# (BN# BigNat#
    y#)) = BigNat# -> BigNat# -> Natural
    subIfGe (BigNat#
    y# BigNat# -> Word# -> BigNat#
    `bigNatAddWord#` Word#
    x#) BigNat#
    m#
    addMod (NatJ# (BN# BigNat#
    m#)) (NatJ# (BN# BigNat#
    x#)) (NatS# Word#
    y#) = BigNat# -> BigNat# -> Natural
    subIfGe (BigNat#
    x# BigNat# -> Word# -> BigNat#
    `bigNatAddWord#` Word#
    y#) BigNat#
    m#
    addMod (NatJ# (BN# BigNat#
    m#)) (NatJ# (BN# BigNat#
    x#)) (NatJ# (BN# BigNat#
    y#)) = BigNat# -> BigNat# -> Natural
    subIfGe (BigNat#
    x# BigNat# -> BigNat# -> BigNat#
    `bigNatAdd` BigNat#
    y#) BigNat#
    m#

    subMod :: Natural -> Natural -> Natural -> Natural
    subMod :: Natural -> Natural -> Natural -> Natural
    subMod (NatS# Word#
    m#) (NatS# Word#
    x#) (NatS# Word#
    y#) =
      if Int# -> Bool
    isTrue# (Word#
    x# Word# -> Word# -> Int#
    `geWord#` Word#
    y#) then Word# -> Natural
    NatS# Word#
    z# else Word# -> Natural
    NatS# (Word#
    z# Word# -> Word# -> Word#
    `plusWord#` Word#
    m#)
      where
        z# :: Word#
    z# = Word#
    x# Word# -> Word# -> Word#
    `minusWord#` Word#
    y#
    subMod NatS#{} Natural
    _ Natural
    _ = Natural
    forall a. a
    brokenInvariant
    subMod (NatJ# (BN# BigNat#
    m#)) (NatS# Word#
    x#) (NatS# Word#
    y#) =
      if Int# -> Bool
    isTrue# (Word#
    x# Word# -> Word# -> Int#
    `geWord#` Word#
    y#)
        then Word# -> Natural
    NatS# (Word#
    x# Word# -> Word# -> Word#
    `minusWord#` Word#
    y#)
        else BigNat# -> Natural
    bigNatToNat (BigNat#
    m# BigNat# -> Word# -> BigNat#
    `bigNatSubWordUnsafe#` (Word#
    y# Word# -> Word# -> Word#
    `minusWord#` Word#
    x#))
    subMod (NatJ# (BN# BigNat#
    m#)) (NatS# Word#
    x#) (NatJ# (BN# BigNat#
    y#)) =
      BigNat# -> Natural
    bigNatToNat (BigNat#
    m# BigNat# -> BigNat# -> BigNat#
    `bigNatSubUnsafe` BigNat#
    y# BigNat# -> Word# -> BigNat#
    `bigNatAddWord#` Word#
    x#)
    subMod NatJ#{} (NatJ# (BN# BigNat#
    x#)) (NatS# Word#
    y#) =
      BigNat# -> Natural
    bigNatToNat (BigNat#
    x# BigNat# -> Word# -> BigNat#
    `bigNatSubWordUnsafe#` Word#
    y#)
    subMod (NatJ# (BN# BigNat#
    m#)) (NatJ# (BN# BigNat#
    x#)) (NatJ# (BN# BigNat#
    y#)) =
      case BigNat#
    x# BigNat# -> BigNat# -> (# (# #) | BigNat# #)
    `bigNatSub` BigNat#
    y# of
        (# (# #) | #) -> BigNat# -> Natural
    bigNatToNat (BigNat#
    m# BigNat# -> BigNat# -> BigNat#
    `bigNatSubUnsafe` BigNat#
    y# BigNat# -> BigNat# -> BigNat#
    `bigNatAdd` BigNat#
    x#)
        (# | BigNat#
    xy# #) -> BigNat# -> Natural
    bigNatToNat BigNat#
    xy#

    negateMod :: Natural -> Natural -> Natural
    negateMod :: Natural -> Natural -> Natural
    negateMod Natural
    _ (NatS# Word#
    0##) = Word# -> Natural
    NatS# Word#
    0##
    negateMod (NatS# Word#
    m#) (NatS# Word#
    x#) = Word# -> Natural
    NatS# (Word#
    m# Word# -> Word# -> Word#
    `minusWord#` Word#
    x#)
    negateMod NatS#{} Natural
    _ = Natural
    forall a. a
    brokenInvariant
    negateMod (NatJ# (BN# BigNat#
    m#)) (NatS# Word#
    x#) = BigNat# -> Natural
    bigNatToNat (BigNat#
    m# BigNat# -> Word# -> BigNat#
    `bigNatSubWordUnsafe#` Word#
    x#)
    negateMod (NatJ# (BN# BigNat#
    m#)) (NatJ# (BN# BigNat#
    x#)) = BigNat# -> Natural
    bigNatToNat (BigNat#
    m# BigNat# -> BigNat# -> BigNat#
    `bigNatSubUnsafe` BigNat#
    x#)

    halfWord :: Word
    halfWord :: Word
    halfWord = Word
    1 Word -> Int -> Word
    forall a. Bits a => a -> Int -> a
    `shiftL` (Word -> Int
    forall b. FiniteBits b => b -> Int
    finiteBitSize (Word
    0 :: Word) Int -> Int -> Int
    forall a. Bits a => a -> Int -> a
    `shiftR` Int
    1)

    mulMod :: Natural -> Natural -> Natural -> Natural
    mulMod :: Natural -> Natural -> Natural -> Natural
    mulMod (NatS# Word#
    m#) (NatS# Word#
    x#) (NatS# Word#
    y#)
      | Word# -> Word
    W# Word#
    m# Word -> Word -> Bool
    forall a. Ord a => a -> a -> Bool
    <= Word
    halfWord = Word# -> Natural
    NatS# (Word# -> Word# -> Word#
    timesWord# Word#
    x# Word#
    y# Word# -> Word# -> Word#
    `remWord#` Word#
    m#)
      | Bool
    otherwise = Word# -> Natural
    NatS# Word#
    r#
      where
        !(# Word#
    hi#, Word#
    lo# #) = Word# -> Word# -> (# Word#, Word# #)
    timesWord2# Word#
    x# Word#
    y#
        !r# :: Word#
    r# = Word# -> Word# -> Word# -> Word#
    remWord2# Word#
    lo# Word#
    hi# Word#
    m#
    mulMod NatS#{} Natural
    _ Natural
    _ = Natural
    forall a. a
    brokenInvariant
    mulMod (NatJ# (BN# BigNat#
    m#)) (NatS# Word#
    x#) (NatS# Word#
    y#) =
      BigNat# -> Natural
    bigNatToNat (Word# -> Word# -> BigNat#
    bigNatFromWord2# Word#
    z1# Word#
    z2# BigNat# -> BigNat# -> BigNat#
    `bigNatRem` BigNat#
    m#)
      where
        !(# Word#
    z1#, Word#
    z2# #) = Word# -> Word# -> (# Word#, Word# #)
    timesWord2# Word#
    x# Word#
    y#
    mulMod (NatJ# (BN# BigNat#
    m#)) (NatS# Word#
    x#) (NatJ# (BN# BigNat#
    y#)) =
      BigNat# -> Natural
    bigNatToNat ((BigNat#
    y# BigNat# -> Word# -> BigNat#
    `bigNatMulWord#` Word#
    x#) BigNat# -> BigNat# -> BigNat#
    `bigNatRem` BigNat#
    m#)
    mulMod (NatJ# (BN# BigNat#
    m#)) (NatJ# (BN# BigNat#
    x#)) (NatS# Word#
    y#) =
      BigNat# -> Natural
    bigNatToNat ((BigNat#
    x# BigNat# -> Word# -> BigNat#
    `bigNatMulWord#` Word#
    y#) BigNat# -> BigNat# -> BigNat#
    `bigNatRem` BigNat#
    m#)
    mulMod (NatJ# (BN# BigNat#
    m#)) (NatJ# (BN# BigNat#
    x#)) (NatJ# (BN# BigNat#
    y#)) =
      BigNat# -> Natural
    bigNatToNat ((BigNat#
    x# BigNat# -> BigNat# -> BigNat#
    `bigNatMul` BigNat#
    y#) BigNat# -> BigNat# -> BigNat#
    `bigNatRem` BigNat#
    m#)

    brokenInvariant :: a
    brokenInvariant :: forall a. a
    brokenInvariant = String -> a
    forall a. HasCallStack => String -> a
    error String
    "argument is larger than modulus"

    instance KnownNat m => Num (Mod m) where
      mx :: Mod m
    mx@(Mod !Natural
    x) + :: Mod m -> Mod m -> Mod m
    + (Mod !Natural
    y) = Natural -> Mod m
    forall (m :: Natural). Natural -> Mod m
    Mod (Natural -> Mod m) -> Natural -> Mod m
    forall a b. (a -> b) -> a -> b
    $ Natural -> Natural -> Natural -> Natural
    addMod (Mod m -> Natural
    forall (n :: Natural) (proxy :: Natural -> *).
    KnownNat n =>
    proxy n -> Natural
    natVal Mod m
    mx) Natural
    x Natural
    y
      {-# INLINE (+) #-}
      mx :: Mod m
    mx@(Mod !Natural
    x) - :: Mod m -> Mod m -> Mod m
    - (Mod !Natural
    y) = Natural -> Mod m
    forall (m :: Natural). Natural -> Mod m
    Mod (Natural -> Mod m) -> Natural -> Mod m
    forall a b. (a -> b) -> a -> b
    $ Natural -> Natural -> Natural -> Natural
    subMod (Mod m -> Natural
    forall (n :: Natural) (proxy :: Natural -> *).
    KnownNat n =>
    proxy n -> Natural
    natVal Mod m
    mx) Natural
    x Natural
    y
      {-# INLINE (-) #-}
      negate :: Mod m -> Mod m
    negate mx :: Mod m
    mx@(Mod !Natural
    x) = Natural -> Mod m
    forall (m :: Natural). Natural -> Mod m
    Mod (Natural -> Mod m) -> Natural -> Mod m
    forall a b. (a -> b) -> a -> b
    $ Natural -> Natural -> Natural
    negateMod (Mod m -> Natural
    forall (n :: Natural) (proxy :: Natural -> *).
    KnownNat n =>
    proxy n -> Natural
    natVal Mod m
    mx) Natural
    x
      {-# INLINE negate #-}
      mx :: Mod m
    mx@(Mod !Natural
    x) * :: Mod m -> Mod m -> Mod m
    * (Mod !Natural
    y) = Natural -> Mod m
    forall (m :: Natural). Natural -> Mod m
    Mod (Natural -> Mod m) -> Natural -> Mod m
    forall a b. (a -> b) -> a -> b
    $ Natural -> Natural -> Natural -> Natural
    mulMod (Mod m -> Natural
    forall (n :: Natural) (proxy :: Natural -> *).
    KnownNat n =>
    proxy n -> Natural
    natVal Mod m
    mx) Natural
    x Natural
    y
      {-# INLINE (*) #-}
      abs :: Mod m -> Mod m
    abs = Mod m -> Mod m
    forall a. a -> a
    id
      {-# INLINE abs #-}
      signum :: Mod m -> Mod m
    signum = Mod m -> Mod m -> Mod m
    forall a b. a -> b -> a
    const Mod m
    x
        where
          x :: Mod m
    x = if Mod m -> Natural
    forall (n :: Natural) (proxy :: Natural -> *).
    KnownNat n =>
    proxy n -> Natural
    natVal Mod m
    x Natural -> Natural -> Bool
    forall a. Ord a => a -> a -> Bool
    > Natural
    1 then Natural -> Mod m
    forall (m :: Natural). Natural -> Mod m
    Mod Natural
    1 else Natural -> Mod m
    forall (m :: Natural). Natural -> Mod m
    Mod Natural
    0
      {-# INLINE signum #-}
      fromInteger :: Integer -> Mod m
    fromInteger Integer
    x = Mod m
    mx
        where
          mx :: Mod m
    mx = Natural -> Mod m
    forall (m :: Natural). Natural -> Mod m
    Mod (Natural -> Mod m) -> Natural -> Mod m
    forall a b. (a -> b) -> a -> b
    $ Integer -> Natural
    forall a. Num a => Integer -> a
    fromInteger (Integer -> Natural) -> Integer -> Natural
    forall a b. (a -> b) -> a -> b
    $ Integer
    x Integer -> Integer -> Integer
    forall a. Integral a => a -> a -> a
    `mod` Natural -> Integer
    forall a. Integral a => a -> Integer
    toInteger (Mod m -> Natural
    forall (n :: Natural) (proxy :: Natural -> *).
    KnownNat n =>
    proxy n -> Natural
    natVal Mod m
    mx)
      {-# INLINE fromInteger #-}

    #ifdef MIN_VERSION_semirings

    instance KnownNat m => Semiring (Mod m) where
      plus :: Mod m -> Mod m -> Mod m
    plus  = Mod m -> Mod m -> Mod m
    forall a. Num a => a -> a -> a
    (+)
      {-# INLINE plus #-}
      times :: Mod m -> Mod m -> Mod m
    times = Mod m -> Mod m -> Mod m
    forall a. Num a => a -> a -> a
    (*)
      {-# INLINE times #-}
      zero :: Mod m
    zero  = Mod m
    mx
        where
          mx :: Mod m
    mx = if Mod m -> Natural
    forall (n :: Natural) (proxy :: Natural -> *).
    KnownNat n =>
    proxy n -> Natural
    natVal Mod m
    mx Natural -> Natural -> Bool
    forall a. Ord a => a -> a -> Bool
    > Natural
    0 then Natural -> Mod m
    forall (m :: Natural). Natural -> Mod m
    Mod Natural
    0 else ArithException -> Mod m
    forall a e. Exception e => e -> a
    throw ArithException
    DivideByZero
      {-# INLINE zero #-}
      one :: Mod m
    one   = Mod m
    mx
        where
          mx :: Mod m
    mx = case Natural
    m Natural -> Natural -> Ordering
    forall a. Ord a => a -> a -> Ordering
    `compare` Natural
    1 of
            Ordering
    LT -> ArithException -> Mod m
    forall a e. Exception e => e -> a
    throw ArithException
    DivideByZero
            Ordering
    EQ -> Natural -> Mod m
    forall (m :: Natural). Natural -> Mod m
    Mod Natural
    0
            Ordering
    GT -> Natural -> Mod m
    forall (m :: Natural). Natural -> Mod m
    Mod Natural
    1
          m :: Natural
    m = Mod m -> Natural
    forall (n :: Natural) (proxy :: Natural -> *).
    KnownNat n =>
    proxy n -> Natural
    natVal Mod m
    mx
      {-# INLINE one #-}
      fromNatural :: Natural -> Mod m
    fromNatural Natural
    x = Mod m
    mx
        where
          mx :: Mod m
    mx = Natural -> Mod m
    forall (m :: Natural). Natural -> Mod m
    Mod (Natural -> Mod m) -> Natural -> Mod m
    forall a b. (a -> b) -> a -> b
    $ Natural
    x Natural -> Natural -> Natural
    forall a. Integral a => a -> a -> a
    `mod` Mod m -> Natural
    forall (n :: Natural) (proxy :: Natural -> *).
    KnownNat n =>
    proxy n -> Natural
    natVal Mod m
    mx
      {-# INLINE fromNatural #-}

    instance KnownNat m => Ring (Mod m) where
      negate :: Mod m -> Mod m
    negate = Mod m -> Mod m
    forall a. Num a => a -> a
    Prelude.negate
      {-# INLINE negate #-}

    -- | 'Mod' @m@ is not even an
    -- <https://en.wikipedia.org/wiki/Integral_domain integral domain> for
    -- <https://en.wikipedia.org/wiki/Composite_number composite> @m@,
    -- much less a <https://en.wikipedia.org/wiki/GCD_domain GCD domain>.
    -- However, 'Data.Euclidean.gcd' and 'Data.Euclidean.lcm' are still meaningful
    -- even for composite @m@, corresponding to a sum and an intersection of
    -- <https://en.wikipedia.org/wiki/Ideal_(ring_theory) ideals>.
    --
    -- The instance is lawful only for
    -- <https://en.wikipedia.org/wiki/Prime_number prime> @m@, otherwise
    -- @'Data.Euclidean.divide' x y@ tries to return any @Just z@ such that @x == y * z@.
    --
    instance KnownNat m => GcdDomain (Mod m) where
      divide :: Mod m -> Mod m -> Maybe (Mod m)
    divide (Mod Natural
    0) Mod m
    _ = Mod m -> Maybe (Mod m)
    forall a. a -> Maybe a
    Just (Natural -> Mod m
    forall (m :: Natural). Natural -> Mod m
    Mod Natural
    0)
      divide Mod m
    _ (Mod Natural
    0) = Maybe (Mod m)
    forall a. Maybe a
    Nothing
      divide mx :: Mod m
    mx@(Mod Natural
    x) (Mod Natural
    y) = case Maybe Natural
    mry of
        Just Natural
    ry -> if Natural
    xr Natural -> Natural -> Bool
    forall a. Eq a => a -> a -> Bool
    == Natural
    0 then Mod m -> Maybe (Mod m)
    forall a. a -> Maybe a
    Just (Natural -> Mod m
    forall (m :: Natural). Natural -> Mod m
    Mod Natural
    xq Mod m -> Mod m -> Mod m
    forall a. Num a => a -> a -> a
    * Natural -> Mod m
    forall (m :: Natural). Natural -> Mod m
    Mod Natural
    ry) else Maybe (Mod m)
    forall a. Maybe a
    Nothing
        Maybe Natural
    Nothing -> Maybe (Mod m)
    forall a. Maybe a
    Nothing
        where
          m :: Natural
    m = Mod m -> Natural
    forall (n :: Natural) (proxy :: Natural -> *).
    KnownNat n =>
    proxy n -> Natural
    natVal Mod m
    mx
          gmy :: Natural
    gmy = Natural -> Natural -> Natural
    forall a. Integral a => a -> a -> a
    Prelude.gcd Natural
    m Natural
    y
          (Natural
    xq, Natural
    xr) = Natural -> Natural -> (Natural, Natural)
    forall a. Integral a => a -> a -> (a, a)
    Prelude.quotRem Natural
    x Natural
    gmy
          mry :: Maybe Natural
    mry = Natural -> Natural -> Maybe Natural
    invertModInternal (Natural
    y Natural -> Natural -> Natural
    forall a. Integral a => a -> a -> a
    `Prelude.quot` Natural
    gmy)  (Natural
    m Natural -> Natural -> Natural
    forall a. Integral a => a -> a -> a
    `Prelude.quot` Natural
    gmy)

      gcd :: Mod m -> Mod m -> Mod m
    gcd (Mod Natural
    x) (Mod Natural
    y) = Mod m
    g
        where
          m :: Natural
    m = Mod m -> Natural
    forall (n :: Natural) (proxy :: Natural -> *).
    KnownNat n =>
    proxy n -> Natural
    natVal Mod m
    g
          g :: Mod m
    g = Natural -> Mod m
    forall (m :: Natural). Natural -> Mod m
    Mod (Natural -> Mod m) -> Natural -> Mod m
    forall a b. (a -> b) -> a -> b
    $ if Natural
    m Natural -> Natural -> Bool
    forall a. Ord a => a -> a -> Bool
    > Natural
    1 then Natural -> Natural -> Natural
    forall a. Integral a => a -> a -> a
    Prelude.gcd (Natural -> Natural -> Natural
    forall a. Integral a => a -> a -> a
    Prelude.gcd Natural
    m Natural
    x) Natural
    y else Natural
    0
      lcm :: Mod m -> Mod m -> Mod m
    lcm (Mod Natural
    x) (Mod Natural
    y) = Mod m
    l
        where
          m :: Natural
    m = Mod m -> Natural
    forall (n :: Natural) (proxy :: Natural -> *).
    KnownNat n =>
    proxy n -> Natural
    natVal Mod m
    l
          l :: Mod m
    l = Natural -> Mod m
    forall (m :: Natural). Natural -> Mod m
    Mod (Natural -> Mod m) -> Natural -> Mod m
    forall a b. (a -> b) -> a -> b
    $ if Natural
    m Natural -> Natural -> Bool
    forall a. Ord a => a -> a -> Bool
    > Natural
    1 then Natural -> Natural -> Natural
    forall a. Integral a => a -> a -> a
    Prelude.lcm (Natural -> Natural -> Natural
    forall a. Integral a => a -> a -> a
    Prelude.gcd Natural
    m Natural
    x) (Natural -> Natural -> Natural
    forall a. Integral a => a -> a -> a
    Prelude.gcd Natural
    m Natural
    y) else Natural
    0
      coprime :: Mod m -> Mod m -> Bool
    coprime Mod m
    x Mod m
    y = Mod m -> Mod m -> Mod m
    forall a. GcdDomain a => a -> a -> a
    Data.Euclidean.gcd Mod m
    x Mod m
    y Mod m -> Mod m -> Bool
    forall a. Eq a => a -> a -> Bool
    == Mod m
    forall a. Semiring a => a
    one

    -- | 'Mod' @m@ is not even an
    -- <https://en.wikipedia.org/wiki/Integral_domain integral domain> for
    -- <https://en.wikipedia.org/wiki/Composite_number composite> @m@,
    -- much less a <https://en.wikipedia.org/wiki/Euclidean_domain Euclidean domain>.
    --
    -- The instance is lawful only for
    -- <https://en.wikipedia.org/wiki/Prime_number prime> @m@, otherwise
    -- we try to do our best:
    -- @'Data.Euclidean.quot' x y@ returns any @z@ such that @x == y * z@,
    -- 'Data.Euclidean.rem' is not always 0, and both can throw 'DivideByZero'.
    --
    instance KnownNat m => Euclidean (Mod m) where
      degree :: Mod m -> Natural
    degree = Mod m -> Natural
    forall (m :: Natural). Mod m -> Natural
    unMod
      {-# INLINABLE degree #-}

      quotRem :: Mod m -> Mod m -> (Mod m, Mod m)
    quotRem (Mod Natural
    0) Mod m
    _ = (Natural -> Mod m
    forall (m :: Natural). Natural -> Mod m
    Mod Natural
    0, Natural -> Mod m
    forall (m :: Natural). Natural -> Mod m
    Mod Natural
    0)
      quotRem Mod m
    _ (Mod Natural
    0) = ArithException -> (Mod m, Mod m)
    forall a e. Exception e => e -> a
    throw ArithException
    DivideByZero
      quotRem mx :: Mod m
    mx@(Mod Natural
    x) (Mod Natural
    y) = case Maybe Natural
    mry of
        Just Natural
    ry -> (Natural -> Mod m
    forall (m :: Natural). Natural -> Mod m
    Mod Natural
    xq Mod m -> Mod m -> Mod m
    forall a. Num a => a -> a -> a
    * Natural -> Mod m
    forall (m :: Natural). Natural -> Mod m
    Mod Natural
    ry, Natural -> Mod m
    forall (m :: Natural). Natural -> Mod m
    Mod Natural
    xr)
        Maybe Natural
    Nothing -> ArithException -> (Mod m, Mod m)
    forall a e. Exception e => e -> a
    throw ArithException
    DivideByZero
        where
          m :: Natural
    m = Mod m -> Natural
    forall (n :: Natural) (proxy :: Natural -> *).
    KnownNat n =>
    proxy n -> Natural
    natVal Mod m
    mx
          gmy :: Natural
    gmy = Natural -> Natural -> Natural
    forall a. Integral a => a -> a -> a
    Prelude.gcd Natural
    m Natural
    y
          (Natural
    xq, Natural
    xr) = Natural -> Natural -> (Natural, Natural)
    forall a. Integral a => a -> a -> (a, a)
    Prelude.quotRem Natural
    x Natural
    gmy
          mry :: Maybe Natural
    mry = Natural -> Natural -> Maybe Natural
    invertModInternal (Natural
    y Natural -> Natural -> Natural
    forall a. Integral a => a -> a -> a
    `Prelude.quot` Natural
    gmy)  (Natural
    m Natural -> Natural -> Natural
    forall a. Integral a => a -> a -> a
    `Prelude.quot` Natural
    gmy)

    -- | 'Mod' @m@ is not even an
    -- <https://en.wikipedia.org/wiki/Integral_domain integral domain> for
    -- <https://en.wikipedia.org/wiki/Composite_number composite> @m@,
    -- much less a <https://en.wikipedia.org/wiki/Field_(mathematics) field>.
    --
    -- The instance is lawful only for
    -- <https://en.wikipedia.org/wiki/Prime_number prime> @m@, otherwise
    -- division by a residue, which is not
    -- <https://en.wikipedia.org/wiki/Coprime_integers coprime>
    -- with the modulus, throws 'DivideByZero'.
    -- Consider using 'invertMod' for non-prime moduli.
    --
    instance KnownNat m => Field (Mod m)

    #endif

    -- | Division by a residue, which is not
    -- <https://en.wikipedia.org/wiki/Coprime_integers coprime>
    -- with the modulus, throws 'DivideByZero'.
    -- Consider using 'invertMod' for non-prime moduli.
    --
    instance KnownNat m => Fractional (Mod m) where
      fromRational :: Rational -> Mod m
    fromRational Rational
    r = case Rational -> Integer
    forall a. Ratio a -> a
    denominator Rational
    r of
        Integer
    1   -> Mod m
    num
        Integer
    den -> Mod m
    num Mod m -> Mod m -> Mod m
    forall a. Fractional a => a -> a -> a
    / Integer -> Mod m
    forall a. Num a => Integer -> a
    fromInteger Integer
    den
        where
          num :: Mod m
    num = Integer -> Mod m
    forall a. Num a => Integer -> a
    fromInteger (Rational -> Integer
    forall a. Ratio a -> a
    numerator Rational
    r)
      {-# INLINE fromRational #-}
      recip :: Mod m -> Mod m
    recip Mod m
    mx = case Mod m -> Maybe (Mod m)
    forall (m :: Natural). KnownNat m => Mod m -> Maybe (Mod m)
    invertMod Mod m
    mx of
        Maybe (Mod m)
    Nothing -> ArithException -> Mod m
    forall a e. Exception e => e -> a
    throw ArithException
    DivideByZero
        Just Mod m
    y  -> Mod m
    y
      {-# INLINE recip #-}

    -- | If an argument is
    -- <https://en.wikipedia.org/wiki/Coprime_integers coprime>
    -- with the modulus, return its modular inverse.
    -- Otherwise return 'Nothing'.
    --
    -- >>> :set -XDataKinds
    -- >>> invertMod 3 :: Mod 10 -- 3 * 7 = 21 ≡ 1 (mod 10)
    -- Just 7
    -- >>> invertMod 4 :: Mod 10 -- 4 and 10 are not coprime
    -- Nothing
    invertMod :: KnownNat m => Mod m -> Maybe (Mod m)
    invertMod :: forall (m :: Natural). KnownNat m => Mod m -> Maybe (Mod m)
    invertMod Mod m
    x = Natural -> Mod m
    forall (m :: Natural). Natural -> Mod m
    Mod (Natural -> Mod m) -> Maybe Natural -> Maybe (Mod m)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> Natural -> Natural -> Maybe Natural
    invertModInternal (Mod m -> Natural
    forall (m :: Natural). Mod m -> Natural
    unMod Mod m
    x) (Mod m -> Natural
    forall (n :: Natural) (proxy :: Natural -> *).
    KnownNat n =>
    proxy n -> Natural
    natVal Mod m
    x)
    {-# INLINABLE invertMod #-}

    invertModInternal
      :: Natural -- Value
      -> Natural -- Modulo
      -> Maybe Natural
    invertModInternal :: Natural -> Natural -> Maybe Natural
    invertModInternal Natural
    x Natural
    m = case Integer -> Natural -> (# Natural | () #)
    integerRecipMod# (Natural -> Integer
    forall a. Integral a => a -> Integer
    toInteger Natural
    x) Natural
    m of
      (# | () #) -> Maybe Natural
    forall a. Maybe a
    Nothing
      (# Natural
    y | #)  -> Natural -> Maybe Natural
    forall a. a -> Maybe a
    Just Natural
    y
    {-# INLINABLE invertModInternal #-}

    -- | Drop-in replacement for 'Prelude.^' with much better performance.
    -- Negative powers are allowed, but may throw 'DivideByZero', if an argument
    -- is not <https://en.wikipedia.org/wiki/Coprime_integers coprime> with the modulus.
    --
    -- >>> :set -XDataKinds
    -- >>> 3 ^% 4 :: Mod 10    -- 3 ^ 4 = 81 ≡ 1 (mod 10)
    -- 1
    -- >>> 3 ^% (-1) :: Mod 10 -- 3 * 7 = 21 ≡ 1 (mod 10)
    -- 7
    -- >>> 4 ^% (-1) :: Mod 10 -- 4 and 10 are not coprime
    -- (*** Exception: divide by zero
    (^%) :: (KnownNat m, Integral a) => Mod m -> a -> Mod m
    Mod m
    mx ^% :: forall (m :: Natural) a.
    (KnownNat m, Integral a) =>
    Mod m -> a -> Mod m
    ^% a
    a
      | a
    a a -> a -> Bool
    forall a. Ord a => a -> a -> Bool
    < a
    0     = case Mod m -> Maybe (Mod m)
    forall (m :: Natural). KnownNat m => Mod m -> Maybe (Mod m)
    invertMod Mod m
    mx of
        Maybe (Mod m)
    Nothing ->  ArithException -> Mod m
    forall a e. Exception e => e -> a
    throw ArithException
    DivideByZero
        Just Mod m
    my ->  Natural -> Mod m
    forall (m :: Natural). Natural -> Mod m
    Mod (Natural -> Mod m) -> Natural -> Mod m
    forall a b. (a -> b) -> a -> b
    $ Natural -> Natural -> Natural -> Natural
    powModNatural (Mod m -> Natural
    forall (m :: Natural). Mod m -> Natural
    unMod Mod m
    my) (a -> Natural
    fromIntegral' (-a
    a)) (Mod m -> Natural
    forall (n :: Natural) (proxy :: Natural -> *).
    KnownNat n =>
    proxy n -> Natural
    natVal Mod m
    mx)
      | Bool
    otherwise = Natural -> Mod m
    forall (m :: Natural). Natural -> Mod m
    Mod (Natural -> Mod m) -> Natural -> Mod m
    forall a b. (a -> b) -> a -> b
    $ Natural -> Natural -> Natural -> Natural
    powModNatural (Mod m -> Natural
    forall (m :: Natural). Mod m -> Natural
    unMod Mod m
    mx) (a -> Natural
    fromIntegral' a
    a)    (Mod m -> Natural
    forall (n :: Natural) (proxy :: Natural -> *).
    KnownNat n =>
    proxy n -> Natural
    natVal Mod m
    mx)
      where
    #if __GLASGOW_HASKELL__ == 900 && __GLASGOW_HASKELL_PATCHLEVEL1__ == 1
        -- Cannot use fromIntegral because of https://gitlab.haskell.org/ghc/ghc/-/issues/19411
        fromIntegral' = fromInteger . toInteger
    #else
        fromIntegral' :: a -> Natural
    fromIntegral' = a -> Natural
    forall a b. (Integral a, Num b) => a -> b
    fromIntegral
    #endif
    {-# INLINABLE [1] (^%) #-}

    {-# SPECIALISE [1] (^%) ::
      KnownNat m => Mod m -> Integer -> Mod m,
      KnownNat m => Mod m -> Natural -> Mod m,
      KnownNat m => Mod m -> Int     -> Mod m,
      KnownNat m => Mod m -> Word    -> Mod m #-}

    {-# RULES
    "powMod/2/Integer"     forall x. x ^% (2 :: Integer) = let u = x in u*u
    "powMod/3/Integer"     forall x. x ^% (3 :: Integer) = let u = x in u*u*u
    "powMod/2/Int"         forall x. x ^% (2 :: Int)     = let u = x in u*u
    "powMod/3/Int"         forall x. x ^% (3 :: Int)     = let u = x in u*u*u
    "powMod/2/Word"        forall x. x ^% (2 :: Word)    = let u = x in u*u
    "powMod/3/Word"        forall x. x ^% (3 :: Word)    = let u = x in u*u*u #-}

    infixr 8 ^%

    wordSize :: Int
    wordSize :: Int
    wordSize = Word -> Int
    forall b. FiniteBits b => b -> Int
    finiteBitSize (Word
    0 :: Word)

    lgWordSize :: Int
    lgWordSize :: Int
    lgWordSize = case Int
    wordSize of
      Int
    32 -> Int
    2 -- 2^2 bytes in word
      Int
    64 -> Int
    3 -- 2^3 bytes in word
      Int
    _  -> String -> Int
    forall a. HasCallStack => String -> a
    error String
    "lgWordSize: unknown architecture"

    -- | No validation checks are performed;
    -- reading untrusted data may corrupt internal invariants.
    instance KnownNat m => Storable (Mod m) where
      sizeOf :: Mod m -> Int
    sizeOf Mod m
    _ = case Proxy# m -> Natural
    forall (n :: Natural). KnownNat n => Proxy# n -> Natural
    natVal' (Proxy# m
    forall {k} (a :: k). Proxy# a
    proxy# :: Proxy# m) of
        NatS#{}  -> Word -> Int
    forall a. Storable a => a -> Int
    sizeOf (Word
    0 :: Word)
        NatJ# (BN# BigNat#
    m#) -> Int# -> Int
    I# (BigNat# -> Int#
    bigNatSize# BigNat#
    m#) Int -> Int -> Int
    forall a. Bits a => a -> Int -> a
    `shiftL` Int
    lgWordSize
      {-# INLINE sizeOf #-}

      alignment :: Mod m -> Int
    alignment Mod m
    _ = Word -> Int
    forall a. Storable a => a -> Int
    alignment (Word
    0 :: Word)
      {-# INLINE alignment #-}

      peek :: Ptr (Mod m) -> IO (Mod m)
    peek (Ptr Addr#
    addr#) = case Proxy# m -> Natural
    forall (n :: Natural). KnownNat n => Proxy# n -> Natural
    natVal' (Proxy# m
    forall {k} (a :: k). Proxy# a
    proxy# :: Proxy# m) of
        NatS#{} -> do
          W# Word#
    w# <- Ptr Word -> IO Word
    forall a. Storable a => Ptr a -> IO a
    peek (Addr# -> Ptr Word
    forall a. Addr# -> Ptr a
    Ptr Addr#
    addr#)
          Mod m -> IO (Mod m)
    forall a. a -> IO a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure (Mod m -> IO (Mod m))
    -> (Natural -> Mod m) -> Natural -> IO (Mod m)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Natural -> Mod m
    forall (m :: Natural). Natural -> Mod m
    Mod (Natural -> IO (Mod m)) -> Natural -> IO (Mod m)
    forall a b. (a -> b) -> a -> b
    $! Word# -> Natural
    NatS# Word#
    w#
        NatJ# (BN# BigNat#
    m#) -> do
          let !(I# Int#
    lgWordSize#) = Int
    lgWordSize
              sz# :: Int#
    sz# = BigNat# -> Int#
    bigNatSize# BigNat#
    m# Int# -> Int# -> Int#
    `iShiftL#` Int#
    lgWordSize#
          BN# BigNat#
    bn <- (State# RealWorld -> (# State# RealWorld, BigNat #)) -> IO BigNat
    forall a. (State# RealWorld -> (# State# RealWorld, a #)) -> IO a
    IO (\State# RealWorld
    token -> case Word#
    -> Addr# -> State# RealWorld -> (# State# RealWorld, BigNat# #)
    forall s. Word# -> Addr# -> State# s -> (# State# s, BigNat# #)
    bigNatFromAddrLE# (Int# -> Word#
    int2Word# Int#
    sz#) Addr#
    addr# State# RealWorld
    token of (# State# RealWorld
    newToken, BigNat#
    bn# #) -> (# State# RealWorld
    newToken, BigNat# -> BigNat
    BN# BigNat#
    bn# #))
          Mod m -> IO (Mod m)
    forall a. a -> IO a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure (Mod m -> IO (Mod m))
    -> (Natural -> Mod m) -> Natural -> IO (Mod m)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Natural -> Mod m
    forall (m :: Natural). Natural -> Mod m
    Mod (Natural -> IO (Mod m)) -> Natural -> IO (Mod m)
    forall a b. (a -> b) -> a -> b
    $! BigNat# -> Natural
    bigNatToNat BigNat#
    bn
      {-# INLINE peek #-}

      poke :: Ptr (Mod m) -> Mod m -> IO ()
    poke (Ptr Addr#
    addr#) (Mod Natural
    x) = case Proxy# m -> Natural
    forall (n :: Natural). KnownNat n => Proxy# n -> Natural
    natVal' (Proxy# m
    forall {k} (a :: k). Proxy# a
    proxy# :: Proxy# m) of
        NatS#{} -> case Natural
    x of
          NatS# Word#
    x# -> Ptr Word -> Word -> IO ()
    forall a. Storable a => Ptr a -> a -> IO ()
    poke (Addr# -> Ptr Word
    forall a. Addr# -> Ptr a
    Ptr Addr#
    addr#) (Word# -> Word
    W# Word#
    x#)
          Natural
    _        -> IO ()
    forall a. a
    brokenInvariant
        NatJ# (BN# BigNat#
    m#) -> case Natural
    x of
          NatS# Word#
    x# -> do
            Ptr Word -> Word -> IO ()
    forall a. Storable a => Ptr a -> a -> IO ()
    poke (Addr# -> Ptr Word
    forall a. Addr# -> Ptr a
    Ptr Addr#
    addr#) (Word# -> Word
    W# Word#
    x#)
            [Int] -> (Int -> IO ()) -> IO ()
    forall (t :: * -> *) (m :: * -> *) a b.
    (Foldable t, Monad m) =>
    t a -> (a -> m b) -> m ()
    forM_ [Int
    1 .. Int
    sz Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Int
    1] ((Int -> IO ()) -> IO ()) -> (Int -> IO ()) -> IO ()
    forall a b. (a -> b) -> a -> b
    $ \Int
    off ->
              Ptr Word -> Int -> Word -> IO ()
    forall a. Storable a => Ptr a -> Int -> a -> IO ()
    pokeElemOff (Addr# -> Ptr Word
    forall a. Addr# -> Ptr a
    Ptr Addr#
    addr#) Int
    off (Word
    0 :: Word)
          NatJ# (BN# BigNat#
    bn) -> do
            Word
    l <- (State# RealWorld -> (# State# RealWorld, Word #)) -> IO Word
    forall a. (State# RealWorld -> (# State# RealWorld, a #)) -> IO a
    IO (\State# RealWorld
    token -> case BigNat#
    -> Addr# -> State# RealWorld -> (# State# RealWorld, Word# #)
    forall s. BigNat# -> Addr# -> State# s -> (# State# s, Word# #)
    bigNatToAddrLE# BigNat#
    bn Addr#
    addr# State# RealWorld
    token of (# State# RealWorld
    newToken, Word#
    l# #) -> (# State# RealWorld
    newToken, Word# -> Word
    W# Word#
    l# #))
            [Int] -> (Int -> IO ()) -> IO ()
    forall (t :: * -> *) (m :: * -> *) a b.
    (Foldable t, Monad m) =>
    t a -> (a -> m b) -> m ()
    forM_ [(Word -> Int
    forall a b. (Integral a, Num b) => a -> b
    fromIntegral :: Word -> Int) Word
    l .. (Int
    sz Int -> Int -> Int
    forall a. Bits a => a -> Int -> a
    `shiftL` Int
    lgWordSize) Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Int
    1] ((Int -> IO ()) -> IO ()) -> (Int -> IO ()) -> IO ()
    forall a b. (a -> b) -> a -> b
    $ \Int
    off ->
              Ptr Word8 -> Int -> Word8 -> IO ()
    forall a. Storable a => Ptr a -> Int -> a -> IO ()
    pokeElemOff (Addr# -> Ptr Word8
    forall a. Addr# -> Ptr a
    Ptr Addr#
    addr#) Int
    off (Word8
    0 :: Word8)
          where
            sz :: Int
    sz = Int# -> Int
    I# (BigNat# -> Int#
    bigNatSize# BigNat#
    m#)
      {-# INLINE poke #-}

    #ifdef MIN_VERSION_vector

    -- | No validation checks are performed;
    -- reading untrusted data may corrupt internal invariants.
    instance KnownNat m => P.Prim (Mod m) where
      sizeOf# :: Mod m -> Int#
    sizeOf# Mod m
    x    = let !(I# Int#
    sz#) = Mod m -> Int
    forall a. Storable a => a -> Int
    sizeOf Mod m
    x    in Int#
    sz#
      {-# INLINE sizeOf# #-}

      alignment# :: Mod m -> Int#
    alignment# Mod m
    x = let !(I# Int#
    a#)  = Mod m -> Int
    forall a. Storable a => a -> Int
    alignment Mod m
    x in Int#
    a#
      {-# INLINE alignment# #-}

      indexByteArray# :: BigNat# -> Int# -> Mod m
    indexByteArray# BigNat#
    arr# Int#
    i' = case Proxy# m -> Natural
    forall (n :: Natural). KnownNat n => Proxy# n -> Natural
    natVal' (Proxy# m
    forall {k} (a :: k). Proxy# a
    proxy# :: Proxy# m) of
        NatS#{} -> Natural -> Mod m
    forall (m :: Natural). Natural -> Mod m
    Mod (Word# -> Natural
    NatS# Word#
    w#)
          where
            !(W# Word#
    w#) = BigNat# -> Int# -> Word
    forall a. Prim a => BigNat# -> Int# -> a
    P.indexByteArray# BigNat#
    arr# Int#
    i'
        NatJ# (BN# BigNat#
    m#) -> Natural -> Mod m
    forall (m :: Natural). Natural -> Mod m
    Mod (Natural -> Mod m) -> Natural -> Mod m
    forall a b. (a -> b) -> a -> b
    $ BigNat# -> Natural
    bigNatToNat ((State# RealWorld -> BigNat#) -> BigNat#
    forall o. (State# RealWorld -> o) -> o
    runRW# (\State# RealWorld
    token -> case Word#
    -> BigNat#
    -> Word#
    -> State# RealWorld
    -> (# State# RealWorld, BigNat# #)
    forall s.
    Word# -> BigNat# -> Word# -> State# s -> (# State# s, BigNat# #)
    bigNatFromByteArrayLE# (Int# -> Word#
    int2Word# Int#
    sz#) BigNat#
    arr# (Int# -> Word#
    int2Word# Int#
    i#) State# RealWorld
    token of (# State# RealWorld
    _, BigNat#
    bn# #) -> BigNat#
    bn#))
          where
            !(I# Int#
    lgWordSize#) = Int
    lgWordSize
            sz# :: Int#
    sz# = BigNat# -> Int#
    bigNatSize# BigNat#
    m# Int# -> Int# -> Int#
    `iShiftL#` Int#
    lgWordSize#
            i# :: Int#
    i# = Int#
    i' Int# -> Int# -> Int#
    *# Int#
    sz#
      {-# INLINE indexByteArray# #-}

      indexOffAddr# :: Addr# -> Int# -> Mod m
    indexOffAddr# Addr#
    arr# Int#
    i' = case Proxy# m -> Natural
    forall (n :: Natural). KnownNat n => Proxy# n -> Natural
    natVal' (Proxy# m
    forall {k} (a :: k). Proxy# a
    proxy# :: Proxy# m) of
        NatS#{} -> Natural -> Mod m
    forall (m :: Natural). Natural -> Mod m
    Mod (Word# -> Natural
    NatS# Word#
    w#)
          where
            !(W# Word#
    w#) = Addr# -> Int# -> Word
    forall a. Prim a => Addr# -> Int# -> a
    P.indexOffAddr# Addr#
    arr# Int#
    i'
        NatJ# (BN# BigNat#
    m#) -> Natural -> Mod m
    forall (m :: Natural). Natural -> Mod m
    Mod (Natural -> Mod m) -> Natural -> Mod m
    forall a b. (a -> b) -> a -> b
    $ BigNat# -> Natural
    bigNatToNat ((State# RealWorld -> BigNat#) -> BigNat#
    forall o. (State# RealWorld -> o) -> o
    runRW# (\State# RealWorld
    token -> case Word#
    -> Addr# -> State# RealWorld -> (# State# RealWorld, BigNat# #)
    forall s. Word# -> Addr# -> State# s -> (# State# s, BigNat# #)
    bigNatFromAddrLE# (Int# -> Word#
    int2Word# Int#
    sz#) (Addr#
    arr# Addr# -> Int# -> Addr#
    `plusAddr#` Int#
    i#) State# RealWorld
    token of (# State# RealWorld
    _, BigNat#
    bn# #) -> BigNat#
    bn#))
          where
            !(I# Int#
    lgWordSize#) = Int
    lgWordSize
            sz# :: Int#
    sz# = BigNat# -> Int#
    bigNatSize# BigNat#
    m# Int# -> Int# -> Int#
    `iShiftL#` Int#
    lgWordSize#
            i# :: Int#
    i# = Int#
    i' Int# -> Int# -> Int#
    *# Int#
    sz#
      {-# INLINE indexOffAddr# #-}

      readByteArray# :: forall s.
    MutableByteArray# s -> Int# -> State# s -> (# State# s, Mod m #)
    readByteArray# MutableByteArray# s
    marr !Int#
    i' State# s
    token = case Proxy# m -> Natural
    forall (n :: Natural). KnownNat n => Proxy# n -> Natural
    natVal' (Proxy# m
    forall {k} (a :: k). Proxy# a
    proxy# :: Proxy# m) of
        NatS#{} -> case MutableByteArray# s -> Int# -> State# s -> (# State# s, Word #)
    forall s.
    MutableByteArray# s -> Int# -> State# s -> (# State# s, Word #)
    forall a s.
    Prim a =>
    MutableByteArray# s -> Int# -> State# s -> (# State# s, a #)
    P.readByteArray# MutableByteArray# s
    marr Int#
    i' State# s
    token of
          (# State# s
    newToken, W# Word#
    w# #) -> (# State# s
    newToken, Natural -> Mod m
    forall (m :: Natural). Natural -> Mod m
    Mod (Word# -> Natural
    NatS# Word#
    w#) #)
        NatJ# (BN# BigNat#
    m#) -> case MutableByteArray# s -> State# s -> (# State# s, BigNat# #)
    forall d.
    MutableByteArray# d -> State# d -> (# State# d, BigNat# #)
    unsafeFreezeByteArray# MutableByteArray# s
    marr State# s
    token of
          (# State# s
    newToken, BigNat#
    arr #) -> case Word# -> BigNat# -> Word# -> State# s -> (# State# s, BigNat# #)
    forall s.
    Word# -> BigNat# -> Word# -> State# s -> (# State# s, BigNat# #)
    bigNatFromByteArrayLE# (Int# -> Word#
    int2Word# Int#
    sz#) BigNat#
    arr (Int# -> Word#
    int2Word# Int#
    i#) State# s
    newToken of
            (# State# s
    veryNewToken, BigNat#
    bn# #) -> (# State# s
    veryNewToken,Natural -> Mod m
    forall (m :: Natural). Natural -> Mod m
    Mod (BigNat# -> Natural
    bigNatToNat BigNat#
    bn#) #)
          where
            !(I# Int#
    lgWordSize#) = Int
    lgWordSize
            sz# :: Int#
    sz# = BigNat# -> Int#
    bigNatSize# BigNat#
    m# Int# -> Int# -> Int#
    `iShiftL#` Int#
    lgWordSize#
            i# :: Int#
    i# = Int#
    i' Int# -> Int# -> Int#
    *# Int#
    sz#
      {-# INLINE readByteArray# #-}

      readOffAddr# :: forall s. Addr# -> Int# -> State# s -> (# State# s, Mod m #)
    readOffAddr# Addr#
    marr !Int#
    i' State# s
    token = case Proxy# m -> Natural
    forall (n :: Natural). KnownNat n => Proxy# n -> Natural
    natVal' (Proxy# m
    forall {k} (a :: k). Proxy# a
    proxy# :: Proxy# m) of
        NatS#{} -> case Addr# -> Int# -> State# s -> (# State# s, Word #)
    forall s. Addr# -> Int# -> State# s -> (# State# s, Word #)
    forall a s.
    Prim a =>
    Addr# -> Int# -> State# s -> (# State# s, a #)
    P.readOffAddr# Addr#
    marr Int#
    i' State# s
    token of
          (# State# s
    newToken, W# Word#
    w# #) -> (# State# s
    newToken, Natural -> Mod m
    forall (m :: Natural). Natural -> Mod m
    Mod (Word# -> Natural
    NatS# Word#
    w#) #)
        NatJ# (BN# BigNat#
    m#) -> case Word# -> Addr# -> State# s -> (# State# s, BigNat# #)
    forall s. Word# -> Addr# -> State# s -> (# State# s, BigNat# #)
    bigNatFromAddrLE# (Int# -> Word#
    int2Word# Int#
    sz#) (Addr#
    marr Addr# -> Int# -> Addr#
    `plusAddr#` Int#
    i#) State# s
    token of
          (# State# s
    newToken, BigNat#
    bn #) -> (# State# s
    newToken, Natural -> Mod m
    forall (m :: Natural). Natural -> Mod m
    Mod (BigNat# -> Natural
    bigNatToNat BigNat#
    bn) #)
          where
            !(I# Int#
    lgWordSize#) = Int
    lgWordSize
            sz# :: Int#
    sz# = BigNat# -> Int#
    bigNatSize# BigNat#
    m# Int# -> Int# -> Int#
    `iShiftL#` Int#
    lgWordSize#
            i# :: Int#
    i# = Int#
    i' Int# -> Int# -> Int#
    *# Int#
    sz#
      {-# INLINE readOffAddr# #-}

      writeByteArray# :: forall s.
    MutableByteArray# s -> Int# -> Mod m -> State# s -> State# s
    writeByteArray# MutableByteArray# s
    marr !Int#
    i' !(Mod Natural
    x) State# s
    token = case Proxy# m -> Natural
    forall (n :: Natural). KnownNat n => Proxy# n -> Natural
    natVal' (Proxy# m
    forall {k} (a :: k). Proxy# a
    proxy# :: Proxy# m) of
        NatS#{} -> case Natural
    x of
          NatS# Word#
    x# -> MutableByteArray# s -> Int# -> Word -> State# s -> State# s
    forall s.
    MutableByteArray# s -> Int# -> Word -> State# s -> State# s
    forall a s.
    Prim a =>
    MutableByteArray# s -> Int# -> a -> State# s -> State# s
    P.writeByteArray# MutableByteArray# s
    marr Int#
    i' (Word# -> Word
    W# Word#
    x#) State# s
    token
          Natural
    _        -> String -> State# s
    forall a. HasCallStack => String -> a
    error String
    "argument is larger than modulus"
        NatJ# (BN# BigNat#
    m#) -> case Natural
    x of
          NatS# Word#
    x# -> case MutableByteArray# s -> Int# -> Word -> State# s -> State# s
    forall s.
    MutableByteArray# s -> Int# -> Word -> State# s -> State# s
    forall a s.
    Prim a =>
    MutableByteArray# s -> Int# -> a -> State# s -> State# s
    P.writeByteArray# MutableByteArray# s
    marr Int#
    i# (Word# -> Word
    W# Word#
    x#) State# s
    token of
            State# s
    newToken -> MutableByteArray# s -> Int# -> Int# -> Word -> State# s -> State# s
    forall s.
    MutableByteArray# s -> Int# -> Int# -> Word -> State# s -> State# s
    forall a s.
    Prim a =>
    MutableByteArray# s -> Int# -> Int# -> a -> State# s -> State# s
    P.setByteArray# MutableByteArray# s
    marr (Int#
    i# Int# -> Int# -> Int#
    +# Int#
    1#) (Int#
    sz# Int# -> Int# -> Int#
    -# Int#
    1#) (Word
    0 :: Word) State# s
    newToken
          NatJ# (BN# BigNat#
    bn) -> case BigNat#
    -> MutableByteArray# s
    -> Word#
    -> State# s
    -> (# State# s, Word# #)
    forall s.
    BigNat#
    -> MutableByteArray# s
    -> Word#
    -> State# s
    -> (# State# s, Word# #)
    bigNatToMutableByteArrayLE# BigNat#
    bn (MutableByteArray# s -> MutableByteArray# s
    forall a b. a -> b
    unsafeCoerce# MutableByteArray# s
    marr) (Int# -> Word#
    int2Word# (Int#
    i# Int# -> Int# -> Int#
    `iShiftL#` Int#
    lgWordSize#)) State# s
    token of
            (# State# s
    newToken, Word#
    l# #) -> MutableByteArray# s
    -> Int# -> Int# -> Word8 -> State# s -> State# s
    forall s.
    MutableByteArray# s
    -> Int# -> Int# -> Word8 -> State# s -> State# s
    forall a s.
    Prim a =>
    MutableByteArray# s -> Int# -> Int# -> a -> State# s -> State# s
    P.setByteArray# MutableByteArray# s
    marr (Int#
    i# Int# -> Int# -> Int#
    `iShiftL#` Int#
    lgWordSize# Int# -> Int# -> Int#
    +# Word# -> Int#
    word2Int# Word#
    l#) (Int#
    sz# Int# -> Int# -> Int#
    `iShiftL#` Int#
    lgWordSize# Int# -> Int# -> Int#
    -# Word# -> Int#
    word2Int# Word#
    l#) (Word8
    0 :: Word8) State# s
    newToken
          where
            !(I# Int#
    lgWordSize#) = Int
    lgWordSize
            !sz :: Int
    sz@(I# Int#
    sz#) = Int# -> Int
    I# (BigNat# -> Int#
    bigNatSize# BigNat#
    m#)
            !(I# Int#
    i#)     = Int# -> Int
    I# Int#
    i' Int -> Int -> Int
    forall a. Num a => a -> a -> a
    * Int
    sz
      {-# INLINE writeByteArray# #-}

      writeOffAddr# :: forall s. Addr# -> Int# -> Mod m -> State# s -> State# s
    writeOffAddr# Addr#
    marr !Int#
    i' !(Mod Natural
    x) State# s
    token = case Proxy# m -> Natural
    forall (n :: Natural). KnownNat n => Proxy# n -> Natural
    natVal' (Proxy# m
    forall {k} (a :: k). Proxy# a
    proxy# :: Proxy# m) of
        NatS#{} -> case Natural
    x of
          NatS# Word#
    x# -> Addr# -> Int# -> Word -> State# s -> State# s
    forall s. Addr# -> Int# -> Word -> State# s -> State# s
    forall a s. Prim a => Addr# -> Int# -> a -> State# s -> State# s
    P.writeOffAddr# Addr#
    marr Int#
    i' (Word# -> Word
    W# Word#
    x#) State# s
    token
          Natural
    _        -> String -> State# s
    forall a. HasCallStack => String -> a
    error String
    "argument is larger than modulus"
        NatJ# (BN# BigNat#
    m#) -> case Natural
    x of
          NatS# Word#
    x# -> case Addr# -> Int# -> Word -> State# s -> State# s
    forall s. Addr# -> Int# -> Word -> State# s -> State# s
    forall a s. Prim a => Addr# -> Int# -> a -> State# s -> State# s
    P.writeOffAddr# Addr#
    marr Int#
    i# (Word# -> Word
    W# Word#
    x#) State# s
    token of
            State# s
    newToken -> Addr# -> Int# -> Int# -> Word -> State# s -> State# s
    forall s. Addr# -> Int# -> Int# -> Word -> State# s -> State# s
    forall a s.
    Prim a =>
    Addr# -> Int# -> Int# -> a -> State# s -> State# s
    P.setOffAddr# Addr#
    marr (Int#
    i# Int# -> Int# -> Int#
    +# Int#
    1#) (Int#
    sz# Int# -> Int# -> Int#
    -# Int#
    1#) (Word
    0 :: Word) State# s
    newToken
          NatJ# (BN# BigNat#
    bn) -> case BigNat# -> Addr# -> State# s -> (# State# s, Word# #)
    forall s. BigNat# -> Addr# -> State# s -> (# State# s, Word# #)
    bigNatToAddrLE# BigNat#
    bn (Addr#
    marr Addr# -> Int# -> Addr#
    `plusAddr#` (Int#
    i# Int# -> Int# -> Int#
    `iShiftL#` Int#
    lgWordSize#)) State# s
    token of
            (# State# s
    newToken, Word#
    l# #) -> Addr# -> Int# -> Int# -> Word8 -> State# s -> State# s
    forall s. Addr# -> Int# -> Int# -> Word8 -> State# s -> State# s
    forall a s.
    Prim a =>
    Addr# -> Int# -> Int# -> a -> State# s -> State# s
    P.setOffAddr# Addr#
    marr (Int#
    i# Int# -> Int# -> Int#
    `iShiftL#` Int#
    lgWordSize# Int# -> Int# -> Int#
    +# Word# -> Int#
    word2Int# Word#
    l#) (Int#
    sz# Int# -> Int# -> Int#
    `iShiftL#` Int#
    lgWordSize# Int# -> Int# -> Int#
    -# Word# -> Int#
    word2Int# Word#
    l#) (Word8
    0 :: Word8) State# s
    newToken
          where
            !(I# Int#
    lgWordSize#) = Int
    lgWordSize
            !sz :: Int
    sz@(I# Int#
    sz#) = Int# -> Int
    I# (BigNat# -> Int#
    bigNatSize# BigNat#
    m#)
            !(I# Int#
    i#)   = Int# -> Int
    I# Int#
    i' Int -> Int -> Int
    forall a. Num a => a -> a -> a
    * Int
    sz
      {-# INLINE writeOffAddr# #-}

      setByteArray# :: forall s.
    MutableByteArray# s
    -> Int# -> Int# -> Mod m -> State# s -> State# s
    setByteArray# !MutableByteArray# s
    _ !Int#
    _ Int#
    0# !Mod m
    _ State# s
    token = State# s
    token
      setByteArray# MutableByteArray# s
    marr Int#
    off Int#
    len mx :: Mod m
    mx@(Mod Natural
    x) State# s
    token = case Proxy# m -> Natural
    forall (n :: Natural). KnownNat n => Proxy# n -> Natural
    natVal' (Proxy# m
    forall {k} (a :: k). Proxy# a
    proxy# :: Proxy# m) of
        NatS#{} -> case Natural
    x of
          NatS# Word#
    x# -> MutableByteArray# s -> Int# -> Int# -> Word -> State# s -> State# s
    forall s.
    MutableByteArray# s -> Int# -> Int# -> Word -> State# s -> State# s
    forall a s.
    Prim a =>
    MutableByteArray# s -> Int# -> Int# -> a -> State# s -> State# s
    P.setByteArray# MutableByteArray# s
    marr Int#
    off Int#
    len (Word# -> Word
    W# Word#
    x#) State# s
    token
          Natural
    _        -> String -> State# s
    forall a. HasCallStack => String -> a
    error String
    "argument is larger than modulus"
        NatJ# (BN# BigNat#
    m#) -> case MutableByteArray# s -> Int# -> Mod m -> State# s -> State# s
    forall s.
    MutableByteArray# s -> Int# -> Mod m -> State# s -> State# s
    forall a s.
    Prim a =>
    MutableByteArray# s -> Int# -> a -> State# s -> State# s
    P.writeByteArray# MutableByteArray# s
    marr Int#
    off Mod m
    mx State# s
    token of
          State# s
    newToken -> Int# -> State# s -> State# s
    doSet (Int#
    sz Int# -> Int# -> Int#
    `iShiftL#` Int#
    lgWordSize#) State# s
    newToken
          where
            !(I# Int#
    lgWordSize#) = Int
    lgWordSize
            sz :: Int#
    sz = BigNat# -> Int#
    bigNatSize# BigNat#
    m#
            off' :: Int#
    off' = (Int#
    off Int# -> Int# -> Int#
    *# Int#
    sz) Int# -> Int# -> Int#
    `iShiftL#` Int#
    lgWordSize#
            len' :: Int#
    len' = (Int#
    len Int# -> Int# -> Int#
    *# Int#
    sz) Int# -> Int# -> Int#
    `iShiftL#` Int#
    lgWordSize#
            doSet :: Int# -> State# s -> State# s
    doSet Int#
    i State# s
    tkn
              | Int# -> Bool
    isTrue# (Int#
    2# Int# -> Int# -> Int#
    *# Int#
    i Int# -> Int# -> Int#
    <# Int#
    len') = case MutableByteArray# s
    -> Int#
    -> MutableByteArray# s
    -> Int#
    -> Int#
    -> State# s
    -> State# s
    forall d.
    MutableByteArray# d
    -> Int#
    -> MutableByteArray# d
    -> Int#
    -> Int#
    -> State# d
    -> State# d
    copyMutableByteArray# MutableByteArray# s
    marr Int#
    off' MutableByteArray# s
    marr (Int#
    off' Int# -> Int# -> Int#
    +# Int#
    i) Int#
    i State# s
    tkn of
                State# s
    tkn' -> Int# -> State# s -> State# s
    doSet (Int#
    2# Int# -> Int# -> Int#
    *# Int#
    i) State# s
    tkn'
              | Bool
    otherwise    = MutableByteArray# s
    -> Int#
    -> MutableByteArray# s
    -> Int#
    -> Int#
    -> State# s
    -> State# s
    forall d.
    MutableByteArray# d
    -> Int#
    -> MutableByteArray# d
    -> Int#
    -> Int#
    -> State# d
    -> State# d
    copyMutableByteArray# MutableByteArray# s
    marr Int#
    off' MutableByteArray# s
    marr (Int#
    off' Int# -> Int# -> Int#
    +# Int#
    i) (Int#
    len' Int# -> Int# -> Int#
    -# Int#
    i) State# s
    tkn
      {-# INLINE setByteArray# #-}

      setOffAddr# :: forall s. Addr# -> Int# -> Int# -> Mod m -> State# s -> State# s
    setOffAddr# !Addr#
    _ !Int#
    _ Int#
    0# !Mod m
    _ State# s
    token = State# s
    token
      setOffAddr# Addr#
    marr Int#
    off Int#
    len mx :: Mod m
    mx@(Mod Natural
    x) State# s
    token = case Proxy# m -> Natural
    forall (n :: Natural). KnownNat n => Proxy# n -> Natural
    natVal' (Proxy# m
    forall {k} (a :: k). Proxy# a
    proxy# :: Proxy# m) of
        NatS#{} -> case Natural
    x of
          NatS# Word#
    x# -> Addr# -> Int# -> Int# -> Word -> State# s -> State# s
    forall s. Addr# -> Int# -> Int# -> Word -> State# s -> State# s
    forall a s.
    Prim a =>
    Addr# -> Int# -> Int# -> a -> State# s -> State# s
    P.setOffAddr# Addr#
    marr Int#
    off Int#
    len (Word# -> Word
    W# Word#
    x#) State# s
    token
          Natural
    _        -> String -> State# s
    forall a. HasCallStack => String -> a
    error String
    "argument is larger than modulus"
        NatJ# (BN# BigNat#
    m#) -> case Addr# -> Int# -> Mod m -> State# s -> State# s
    forall s. Addr# -> Int# -> Mod m -> State# s -> State# s
    forall a s. Prim a => Addr# -> Int# -> a -> State# s -> State# s
    P.writeOffAddr# Addr#
    marr Int#
    off Mod m
    mx State# s
    token of
          State# s
    newToken -> Int# -> State# s -> State# s
    doSet (Int#
    sz Int# -> Int# -> Int#
    `iShiftL#` Int#
    lgWordSize#) State# s
    newToken
          where
            !(I# Int#
    lgWordSize#) = Int
    lgWordSize
            sz :: Int#
    sz = BigNat# -> Int#
    bigNatSize# BigNat#
    m#
            off' :: Int#
    off' = (Int#
    off Int# -> Int# -> Int#
    *# Int#
    sz) Int# -> Int# -> Int#
    `iShiftL#` Int#
    lgWordSize#
            len' :: Int#
    len' = (Int#
    len Int# -> Int# -> Int#
    *# Int#
    sz) Int# -> Int# -> Int#
    `iShiftL#` Int#
    lgWordSize#
            doSet :: Int# -> State# s -> State# s
    doSet Int#
    i State# s
    tkn -- = tkn
              | Int# -> Bool
    isTrue# (Int#
    2# Int# -> Int# -> Int#
    *# Int#
    i Int# -> Int# -> Int#
    <# Int#
    len') = case ST s ()
    -> State# (PrimState (ST s)) -> (# State# (PrimState (ST s)), () #)
    forall a.
    ST s a
    -> State# (PrimState (ST s)) -> (# State# (PrimState (ST s)), a #)
    forall (m :: * -> *) a.
    PrimBase m =>
    m a -> State# (PrimState m) -> (# State# (PrimState m), a #)
    internal (IO () -> ST s ()
    forall (m :: * -> *) a. PrimMonad m => IO a -> m a
    unsafeIOToPrim (Ptr Any -> Ptr Any -> Int -> IO ()
    forall a. Ptr a -> Ptr a -> Int -> IO ()
    copyBytes (Addr# -> Ptr Any
    forall a. Addr# -> Ptr a
    Ptr (Addr#
    marr Addr# -> Int# -> Addr#
    `plusAddr#` (Int#
    off' Int# -> Int# -> Int#
    +# Int#
    i))) (Addr# -> Ptr Any
    forall a. Addr# -> Ptr a
    Ptr (Addr#
    marr Addr# -> Int# -> Addr#
    `plusAddr#` Int#
    off')) (Int# -> Int
    I# Int#
    i)) :: ST s ()) State# s
    State# (PrimState (ST s))
    tkn of
                (# State# (PrimState (ST s))
    tkn', () #) -> Int# -> State# s -> State# s
    doSet (Int#
    2# Int# -> Int# -> Int#
    *# Int#
    i) State# s
    State# (PrimState (ST s))
    tkn'
              | Bool
    otherwise    = case ST s ()
    -> State# (PrimState (ST s)) -> (# State# (PrimState (ST s)), () #)
    forall a.
    ST s a
    -> State# (PrimState (ST s)) -> (# State# (PrimState (ST s)), a #)
    forall (m :: * -> *) a.
    PrimBase m =>
    m a -> State# (PrimState m) -> (# State# (PrimState m), a #)
    internal (IO () -> ST s ()
    forall (m :: * -> *) a. PrimMonad m => IO a -> m a
    unsafeIOToPrim (Ptr Any -> Ptr Any -> Int -> IO ()
    forall a. Ptr a -> Ptr a -> Int -> IO ()
    copyBytes (Addr# -> Ptr Any
    forall a. Addr# -> Ptr a
    Ptr (Addr#
    marr Addr# -> Int# -> Addr#
    `plusAddr#` (Int#
    off' Int# -> Int# -> Int#
    +# Int#
    i))) (Addr# -> Ptr Any
    forall a. Addr# -> Ptr a
    Ptr (Addr#
    marr Addr# -> Int# -> Addr#
    `plusAddr#` Int#
    off')) (Int# -> Int
    I# (Int#
    len' Int# -> Int# -> Int#
    -# Int#
    i))) :: ST s ()) State# s
    State# (PrimState (ST s))
    tkn of
                (# State# (PrimState (ST s))
    tkn', () #) -> State# s
    State# (PrimState (ST s))
    tkn'
      {-# INLINE setOffAddr# #-}

    -- | Unboxed vectors of 'Mod' cause more nursery allocations
    -- than boxed ones, but reduce pressure on the garbage collector,
    -- especially for large vectors.
    newtype instance U.MVector s (Mod m) = ModMVec (P.MVector s (Mod m))

    -- | Unboxed vectors of 'Mod' cause more nursery allocations
    -- than boxed ones, but reduce pressure on the garbage collector,
    -- especially for large vectors.
    newtype instance U.Vector    (Mod m) = ModVec  (P.Vector (Mod m))

    -- | No validation checks are performed;
    -- reading untrusted data may corrupt internal invariants.
    instance KnownNat m => U.Unbox (Mod m)

    -- | No validation checks are performed;
    -- reading untrusted data may corrupt internal invariants.
    instance KnownNat m => M.MVector U.MVector (Mod m) where
      {-# INLINE basicLength #-}
      {-# INLINE basicUnsafeSlice #-}
      {-# INLINE basicOverlaps #-}
      {-# INLINE basicUnsafeNew #-}
      {-# INLINE basicInitialize #-}
      {-# INLINE basicUnsafeReplicate #-}
      {-# INLINE basicUnsafeRead #-}
      {-# INLINE basicUnsafeWrite #-}
      {-# INLINE basicClear #-}
      {-# INLINE basicSet #-}
      {-# INLINE basicUnsafeCopy #-}
      {-# INLINE basicUnsafeGrow #-}
      basicLength :: forall s. MVector s (Mod m) -> Int
    basicLength (ModMVec MVector s (Mod m)
    v) = MVector s (Mod m) -> Int
    forall s. MVector s (Mod m) -> Int
    forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
    M.basicLength MVector s (Mod m)
    v
      basicUnsafeSlice :: forall s. Int -> Int -> MVector s (Mod m) -> MVector s (Mod m)
    basicUnsafeSlice Int
    i Int
    n (ModMVec MVector s (Mod m)
    v) = MVector s (Mod m) -> MVector s (Mod m)
    forall s (m :: Natural). MVector s (Mod m) -> MVector s (Mod m)
    ModMVec (MVector s (Mod m) -> MVector s (Mod m))
    -> MVector s (Mod m) -> MVector s (Mod m)
    forall a b. (a -> b) -> a -> b
    $ Int -> Int -> MVector s (Mod m) -> MVector s (Mod m)
    forall s. Int -> Int -> MVector s (Mod m) -> MVector s (Mod m)
    forall (v :: * -> * -> *) a s.
    MVector v a =>
    Int -> Int -> v s a -> v s a
    M.basicUnsafeSlice Int
    i Int
    n MVector s (Mod m)
    v
      basicOverlaps :: forall s. MVector s (Mod m) -> MVector s (Mod m) -> Bool
    basicOverlaps (ModMVec MVector s (Mod m)
    v1) (ModMVec MVector s (Mod m)
    v2) = MVector s (Mod m) -> MVector s (Mod m) -> Bool
    forall s. MVector s (Mod m) -> MVector s (Mod m) -> Bool
    forall (v :: * -> * -> *) a s.
    MVector v a =>
    v s a -> v s a -> Bool
    M.basicOverlaps MVector s (Mod m)
    v1 MVector s (Mod m)
    v2
      basicUnsafeNew :: forall s. Int -> ST s (MVector s (Mod m))
    basicUnsafeNew Int
    n = MVector s (Mod m) -> MVector s (Mod m)
    forall s (m :: Natural). MVector s (Mod m) -> MVector s (Mod m)
    ModMVec (MVector s (Mod m) -> MVector s (Mod m))
    -> ST s (MVector s (Mod m)) -> ST s (MVector s (Mod m))
    forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
    `liftM` Int -> ST s (MVector s (Mod m))
    forall s. Int -> ST s (MVector s (Mod m))
    forall (v :: * -> * -> *) a s. MVector v a => Int -> ST s (v s a)
    M.basicUnsafeNew Int
    n
      basicInitialize :: forall s. MVector s (Mod m) -> ST s ()
    basicInitialize (ModMVec MVector s (Mod m)
    v) = MVector s (Mod m) -> ST s ()
    forall s. MVector s (Mod m) -> ST s ()
    forall (v :: * -> * -> *) a s. MVector v a => v s a -> ST s ()
    M.basicInitialize MVector s (Mod m)
    v
      basicUnsafeReplicate :: forall s. Int -> Mod m -> ST s (MVector s (Mod m))
    basicUnsafeReplicate Int
    n Mod m
    x = MVector s (Mod m) -> MVector s (Mod m)
    forall s (m :: Natural). MVector s (Mod m) -> MVector s (Mod m)
    ModMVec (MVector s (Mod m) -> MVector s (Mod m))
    -> ST s (MVector s (Mod m)) -> ST s (MVector s (Mod m))
    forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
    `liftM` Int -> Mod m -> ST s (MVector s (Mod m))
    forall s. Int -> Mod m -> ST s (MVector s (Mod m))
    forall (v :: * -> * -> *) a s.
    MVector v a =>
    Int -> a -> ST s (v s a)
    M.basicUnsafeReplicate Int
    n Mod m
    x
      basicUnsafeRead :: forall s. MVector s (Mod m) -> Int -> ST s (Mod m)
    basicUnsafeRead (ModMVec MVector s (Mod m)
    v) Int
    i = MVector s (Mod m) -> Int -> ST s (Mod m)
    forall s. MVector s (Mod m) -> Int -> ST s (Mod m)
    forall (v :: * -> * -> *) a s.
    MVector v a =>
    v s a -> Int -> ST s a
    M.basicUnsafeRead MVector s (Mod m)
    v Int
    i
      basicUnsafeWrite :: forall s. MVector s (Mod m) -> Int -> Mod m -> ST s ()
    basicUnsafeWrite (ModMVec MVector s (Mod m)
    v) Int
    i Mod m
    x = MVector s (Mod m) -> Int -> Mod m -> ST s ()
    forall s. MVector s (Mod m) -> Int -> Mod m -> ST s ()
    forall (v :: * -> * -> *) a s.
    MVector v a =>
    v s a -> Int -> a -> ST s ()
    M.basicUnsafeWrite MVector s (Mod m)
    v Int
    i Mod m
    x
      basicClear :: forall s. MVector s (Mod m) -> ST s ()
    basicClear (ModMVec MVector s (Mod m)
    v) = MVector s (Mod m) -> ST s ()
    forall s. MVector s (Mod m) -> ST s ()
    forall (v :: * -> * -> *) a s. MVector v a => v s a -> ST s ()
    M.basicClear MVector s (Mod m)
    v
      basicSet :: forall s. MVector s (Mod m) -> Mod m -> ST s ()
    basicSet (ModMVec MVector s (Mod m)
    v) Mod m
    x = MVector s (Mod m) -> Mod m -> ST s ()
    forall s. MVector s (Mod m) -> Mod m -> ST s ()
    forall (v :: * -> * -> *) a s. MVector v a => v s a -> a -> ST s ()
    M.basicSet MVector s (Mod m)
    v Mod m
    x
      basicUnsafeCopy :: forall s. MVector s (Mod m) -> MVector s (Mod m) -> ST s ()
    basicUnsafeCopy (ModMVec MVector s (Mod m)
    v1) (ModMVec MVector s (Mod m)
    v2) = MVector s (Mod m) -> MVector s (Mod m) -> ST s ()
    forall s. MVector s (Mod m) -> MVector s (Mod m) -> ST s ()
    forall (v :: * -> * -> *) a s.
    MVector v a =>
    v s a -> v s a -> ST s ()
    M.basicUnsafeCopy MVector s (Mod m)
    v1 MVector s (Mod m)
    v2
      basicUnsafeMove :: forall s. MVector s (Mod m) -> MVector s (Mod m) -> ST s ()
    basicUnsafeMove (ModMVec MVector s (Mod m)
    v1) (ModMVec MVector s (Mod m)
    v2) = MVector s (Mod m) -> MVector s (Mod m) -> ST s ()
    forall s. MVector s (Mod m) -> MVector s (Mod m) -> ST s ()
    forall (v :: * -> * -> *) a s.
    MVector v a =>
    v s a -> v s a -> ST s ()
    M.basicUnsafeMove MVector s (Mod m)
    v1 MVector s (Mod m)
    v2
      basicUnsafeGrow :: forall s. MVector s (Mod m) -> Int -> ST s (MVector s (Mod m))
    basicUnsafeGrow (ModMVec MVector s (Mod m)
    v) Int
    n = MVector s (Mod m) -> MVector s (Mod m)
    forall s (m :: Natural). MVector s (Mod m) -> MVector s (Mod m)
    ModMVec (MVector s (Mod m) -> MVector s (Mod m))
    -> ST s (MVector s (Mod m)) -> ST s (MVector s (Mod m))
    forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
    `liftM` MVector s (Mod m) -> Int -> ST s (MVector s (Mod m))
    forall s. MVector s (Mod m) -> Int -> ST s (MVector s (Mod m))
    forall (v :: * -> * -> *) a s.
    MVector v a =>
    v s a -> Int -> ST s (v s a)
    M.basicUnsafeGrow MVector s (Mod m)
    v Int
    n

    -- | No validation checks are performed;
    -- reading untrusted data may corrupt internal invariants.
    instance KnownNat m => G.Vector U.Vector (Mod m) where
      {-# INLINE basicUnsafeFreeze #-}
      {-# INLINE basicUnsafeThaw #-}
      {-# INLINE basicLength #-}
      {-# INLINE basicUnsafeSlice #-}
      {-# INLINE basicUnsafeIndexM #-}
      {-# INLINE elemseq #-}
      basicUnsafeFreeze :: forall s. Mutable Vector s (Mod m) -> ST s (Vector (Mod m))
    basicUnsafeFreeze (ModMVec MVector s (Mod m)
    v) = Vector (Mod m) -> Vector (Mod m)
    forall (m :: Natural). Vector (Mod m) -> Vector (Mod m)
    ModVec (Vector (Mod m) -> Vector (Mod m))
    -> ST s (Vector (Mod m)) -> ST s (Vector (Mod m))
    forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
    `liftM` Mutable Vector s (Mod m) -> ST s (Vector (Mod m))
    forall s. Mutable Vector s (Mod m) -> ST s (Vector (Mod m))
    forall (v :: * -> *) a s. Vector v a => Mutable v s a -> ST s (v a)
    G.basicUnsafeFreeze Mutable Vector s (Mod m)
    MVector s (Mod m)
    v
      basicUnsafeThaw :: forall s. Vector (Mod m) -> ST s (Mutable Vector s (Mod m))
    basicUnsafeThaw (ModVec Vector (Mod m)
    v) = MVector s (Mod m) -> MVector s (Mod m)
    forall s (m :: Natural). MVector s (Mod m) -> MVector s (Mod m)
    ModMVec (MVector s (Mod m) -> MVector s (Mod m))
    -> ST s (MVector s (Mod m)) -> ST s (MVector s (Mod m))
    forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
    `liftM` Vector (Mod m) -> ST s (Mutable Vector s (Mod m))
    forall s. Vector (Mod m) -> ST s (Mutable Vector s (Mod m))
    forall (v :: * -> *) a s. Vector v a => v a -> ST s (Mutable v s a)
    G.basicUnsafeThaw Vector (Mod m)
    v
      basicLength :: Vector (Mod m) -> Int
    basicLength (ModVec Vector (Mod m)
    v) = Vector (Mod m) -> Int
    forall (v :: * -> *) a. Vector v a => v a -> Int
    G.basicLength Vector (Mod m)
    v
      basicUnsafeSlice :: Int -> Int -> Vector (Mod m) -> Vector (Mod m)
    basicUnsafeSlice Int
    i Int
    n (ModVec Vector (Mod m)
    v) = Vector (Mod m) -> Vector (Mod m)
    forall (m :: Natural). Vector (Mod m) -> Vector (Mod m)
    ModVec (Vector (Mod m) -> Vector (Mod m))
    -> Vector (Mod m) -> Vector (Mod m)
    forall a b. (a -> b) -> a -> b
    $ Int -> Int -> Vector (Mod m) -> Vector (Mod m)
    forall (v :: * -> *) a. Vector v a => Int -> Int -> v a -> v a
    G.basicUnsafeSlice Int
    i Int
    n Vector (Mod m)
    v
      basicUnsafeIndexM :: Vector (Mod m) -> Int -> Box (Mod m)
    basicUnsafeIndexM (ModVec Vector (Mod m)
    v) Int
    i = Vector (Mod m) -> Int -> Box (Mod m)
    forall (v :: * -> *) a. Vector v a => v a -> Int -> Box a
    G.basicUnsafeIndexM Vector (Mod m)
    v Int
    i
      basicUnsafeCopy :: forall s. Mutable Vector s (Mod m) -> Vector (Mod m) -> ST s ()
    basicUnsafeCopy (ModMVec MVector s (Mod m)
    mv) (ModVec Vector (Mod m)
    v) = Mutable Vector s (Mod m) -> Vector (Mod m) -> ST s ()
    forall s. Mutable Vector s (Mod m) -> Vector (Mod m) -> ST s ()
    forall (v :: * -> *) a s.
    Vector v a =>
    Mutable v s a -> v a -> ST s ()
    G.basicUnsafeCopy Mutable Vector s (Mod m)
    MVector s (Mod m)
    mv Vector (Mod m)
    v
      elemseq :: forall b. Vector (Mod m) -> Mod m -> b -> b
    elemseq Vector (Mod m)
    _ = Mod m -> b -> b
    forall a b. a -> b -> b
    seq

    #endif