///|
/// A fixed, positive Int modulus. A tag must always return the same modulus.
pub(open) trait Modulus {
  fn modulus() -> Int
}

///|
/// Independent mutable modulus shared by all values of a dynamic tag.
pub struct ModState {
  priv mut modulus_value : Int
} derive(Debug)

///|
pub fn ModState::new(modulus? : Int = 998244353) -> ModState {
  @internal.require(modulus >= 1)
  { modulus_value: modulus, }
}

///|
pub fn ModState::set_mod(self : ModState, modulus : Int) -> Unit {
  @internal.require(modulus >= 1)
  self.modulus_value = modulus
}

///|
pub fn ModState::mod(self : ModState) -> Int {
  self.modulus_value
}

///|
/// Each tag must return the same ModState instance on every call.
/// Changing its modulus invalidates all existing residues for that tag, as in ACL.
pub(open) trait DynamicModulus {
  fn state() -> ModState
}

///|
pub(all) struct Mod998244353 {} derive(Debug)

///|
pub(all) struct Mod1000000007 {} derive(Debug)

///|
pub(all) struct DefaultId {} derive(Debug)

///|
pub impl Modulus for Mod998244353 with fn modulus() {
  998244353
}

///|
pub impl Modulus for Mod1000000007 with fn modulus() {
  1000000007
}

///|
let default_state : ModState = ModState::new()

///|
pub impl DynamicModulus for DefaultId with fn state() {
  default_state
}

///|
pub type ModInt998244353 = StaticModInt[Mod998244353]

///|
pub type ModInt1000000007 = StaticModInt[Mod1000000007]

///|
pub type ModInt = DynamicModInt[DefaultId]

///|
/// Immutable residue in [0, modulus).
pub struct StaticModInt[_] {
  priv value : Int
}

///|
pub fn[M : Modulus] StaticModInt::mod(_self : StaticModInt[M]) -> Int {
  M::modulus()
}

///|
pub fn[M : Modulus] StaticModInt::new(value : Int) -> StaticModInt[M] {
  StaticModInt::from_int64(value.to_int64())
}

///|
pub fn[M : Modulus] StaticModInt::from_int64(value : Int64) -> StaticModInt[M] {
  let m = M::modulus()
  @internal.require(m >= 1)
  { value: @internal.safe_mod(value, m.to_int64()).to_int(), }
}

///|
pub fn[M : Modulus] StaticModInt::from_uint(value : UInt) -> StaticModInt[M] {
  StaticModInt::from_uint64(value.to_uint64())
}

///|
pub fn[M : Modulus] StaticModInt::from_uint64(
  value : UInt64,
) -> StaticModInt[M] {
  let m = M::modulus()
  @internal.require(m >= 1)
  { value: (value % m.to_uint64()).to_int(), }
}

///|
/// No modular reduction; requires 0 <= value < modulus.
pub fn[M : Modulus] StaticModInt::raw(value : Int) -> StaticModInt[M] {
  @internal.require(0 <= value && value < M::modulus())
  { value, }
}

///|
pub fn[M] StaticModInt::val(self : StaticModInt[M]) -> Int {
  self.value
}

///|
pub fn[M : Modulus] StaticModInt::pow(
  self : StaticModInt[M],
  n : Int64,
) -> StaticModInt[M] {
  { value: @internal.pow_mod(self.value.to_int64(), n, M::modulus()).to_int(), }
}

///|
pub fn[M : Modulus] StaticModInt::inv(
  self : StaticModInt[M],
) -> StaticModInt[M] {
  let (g, inverse) = @internal.inv_gcd(
    self.value.to_int64(),
    M::modulus().to_int64(),
  )
  @internal.require(g == 1L)
  { value: inverse.to_int(), }
}

///|
pub impl[M] Eq for StaticModInt[M] with fn equal(a, b) {
  a.value == b.value
}

///|
pub impl[M] Debug for StaticModInt[M] with fn to_repr(self) {
  @debug.Repr(self.value)
}

///|
pub impl[M : Modulus] Default for StaticModInt[M] with fn default() {
  StaticModInt::new(0)
}

///|
pub impl[M : Modulus] @algebra.Zero for StaticModInt[M] with fn zero() {
  StaticModInt::new(0)
}

///|
pub impl[M : Modulus] Add for StaticModInt[M] with fn add(a, b) {
  let m = M::modulus().to_int64()
  let sum = a.value.to_int64() + b.value.to_int64()
  { value: (if sum >= m { sum - m } else { sum }).to_int(), }
}

///|
pub impl[M : Modulus] Sub for StaticModInt[M] with fn sub(a, b) {
  let diff = a.value - b.value
  { value: if diff < 0 { diff + M::modulus() } else { diff }, }
}

///|
pub impl[M : Modulus] Mul for StaticModInt[M] with fn mul(a, b) {
  {
    value: (a.value.to_int64() * b.value.to_int64() % M::modulus().to_int64()).to_int(),
  }
}

///|
pub impl[M : Modulus] Div for StaticModInt[M] with fn div(a, b) {
  a * b.inv()
}

///|
pub impl[M : Modulus] Neg for StaticModInt[M] with fn neg(self) {
  { value: if self.value == 0 { 0 } else { M::modulus() - self.value }, }
}

///|
/// Immutable residue in [0, modulus).
pub struct DynamicModInt[_] {
  priv value : Int
}

///|
pub fn[M : DynamicModulus] DynamicModInt::mod(_self : DynamicModInt[M]) -> Int {
  M::state().mod()
}

///|
pub fn[M : DynamicModulus] DynamicModInt::new(value : Int) -> DynamicModInt[M] {
  DynamicModInt::from_int64(value.to_int64())
}

///|
pub fn[M : DynamicModulus] DynamicModInt::from_int64(
  value : Int64,
) -> DynamicModInt[M] {
  let m = M::state().mod()
  @internal.require(m >= 1)
  { value: @internal.safe_mod(value, m.to_int64()).to_int(), }
}

///|
pub fn[M : DynamicModulus] DynamicModInt::from_uint(
  value : UInt,
) -> DynamicModInt[M] {
  DynamicModInt::from_uint64(value.to_uint64())
}

///|
pub fn[M : DynamicModulus] DynamicModInt::from_uint64(
  value : UInt64,
) -> DynamicModInt[M] {
  let m = M::state().mod()
  @internal.require(m >= 1)
  { value: (value % m.to_uint64()).to_int(), }
}

///|
/// No modular reduction; requires 0 <= value < modulus.
pub fn[M : DynamicModulus] DynamicModInt::raw(value : Int) -> DynamicModInt[M] {
  @internal.require(0 <= value && value < M::state().mod())
  { value, }
}

///|
pub fn[M] DynamicModInt::val(self : DynamicModInt[M]) -> Int {
  self.value
}

///|
pub fn[M : DynamicModulus] DynamicModInt::pow(
  self : DynamicModInt[M],
  n : Int64,
) -> DynamicModInt[M] {
  {
    value: @internal.pow_mod(self.value.to_int64(), n, M::state().mod()).to_int(),
  }
}

///|
pub fn[M : DynamicModulus] DynamicModInt::inv(
  self : DynamicModInt[M],
) -> DynamicModInt[M] {
  let (g, inverse) = @internal.inv_gcd(
    self.value.to_int64(),
    M::state().mod().to_int64(),
  )
  @internal.require(g == 1L)
  { value: inverse.to_int(), }
}

///|
pub impl[M] Eq for DynamicModInt[M] with fn equal(a, b) {
  a.value == b.value
}

///|
pub impl[M] Debug for DynamicModInt[M] with fn to_repr(self) {
  @debug.Repr(self.value)
}

///|
pub impl[M : DynamicModulus] Default for DynamicModInt[M] with fn default() {
  DynamicModInt::new(0)
}

///|
pub impl[M : DynamicModulus] @algebra.Zero for DynamicModInt[M] with fn zero() {
  DynamicModInt::new(0)
}

///|
pub impl[M : DynamicModulus] Add for DynamicModInt[M] with fn add(a, b) {
  let m = M::state().mod().to_int64()
  let sum = a.value.to_int64() + b.value.to_int64()
  { value: (if sum >= m { sum - m } else { sum }).to_int(), }
}

///|
pub impl[M : DynamicModulus] Sub for DynamicModInt[M] with fn sub(a, b) {
  let diff = a.value - b.value
  { value: if diff < 0 { diff + M::state().mod() } else { diff }, }
}

///|
pub impl[M : DynamicModulus] Mul for DynamicModInt[M] with fn mul(a, b) {
  {
    value: (a.value.to_int64() *
    b.value.to_int64() %
    M::state().mod().to_int64()).to_int(),
  }
}

///|
pub impl[M : DynamicModulus] Div for DynamicModInt[M] with fn div(a, b) {
  a * b.inv()
}

///|
pub impl[M : DynamicModulus] Neg for DynamicModInt[M] with fn neg(self) {
  { value: if self.value == 0 { 0 } else { M::state().mod() - self.value }, }
}

///|
/// Sets the modulus of the default ModInt tag. Custom tags use ModState::set_mod.
pub fn set_mod(modulus : Int) -> Unit {
  default_state.set_mod(modulus)
}