1# from titan_pylib.math.mod_int import ModInt
2from typing import Union
3
4
5class ModInt:
6
7 mod = -1
8
9 __slots__ = "val"
10
11 @classmethod
12 def _inv(cls, a: int) -> int:
13 res = 1
14 b = cls.self.mod - 2
15 while b:
16 if b & 1:
17 res = res * a % cls.mod
18 a = a * a % cls.mod
19 b >>= 1
20 return res
21
22 @classmethod
23 def get_mod(cls) -> int:
24 return cls.mod
25
26 def __init__(self, val: int) -> None:
27 self.val = val if 0 <= val < self.mod else val % self.mod
28
29 def __add__(self, other: Union[int, "ModInt"]) -> "ModInt":
30 return ModInt(self.val + int(other))
31
32 def __sub__(self, other: Union[int, "ModInt"]) -> "ModInt":
33 return ModInt(self.val - int(other))
34
35 def __mul__(self, other: Union[int, "ModInt"]) -> "ModInt":
36 return ModInt(self.val * int(other))
37
38 def __pow__(self, other: Union[int, "ModInt"]) -> "ModInt":
39 return ModInt(pow(self.val, int(other), self.mod))
40
41 def __truediv__(self, other: Union[int, "ModInt"]) -> "ModInt":
42 return ModInt(self.val * (self._inv(int(other))))
43
44 # __iadd__ = __add__
45 # __isub__ = __sub__
46 # __imul__ = __mul__
47 # __ipow__ = __pow__
48 # __itruediv__ = __truediv__
49
50 def __iadd__(self, other: Union[int, "ModInt"]) -> "ModInt":
51 self.val += int(other)
52 self.val %= self.mod
53 return self
54
55 def __isub__(self, other: Union[int, "ModInt"]) -> "ModInt":
56 self.val -= int(other)
57 self.val %= self.mod
58 return self
59
60 def __imul__(self, other: Union[int, "ModInt"]) -> "ModInt":
61 self.val *= int(other)
62 self.val %= self.mod
63 return self
64
65 def __ipow__(self, other: Union[int, "ModInt"]) -> "ModInt":
66 self.val = pow(self.val, int(other), self.mod)
67 return self
68
69 def __itruediv__(self, other: Union[int, "ModInt"]) -> "ModInt":
70 self.val *= self._inv(int(other))
71 self.val %= self.mod
72 return self
73
74 __radd__ = __add__
75 __rmul__ = __mul__
76
77 def __rsub__(self, other: Union[int, "ModInt"]) -> "ModInt":
78 return ModInt(int(other) - self.val)
79
80 def __rpow__(self, other: Union[int, "ModInt"]) -> "ModInt":
81 return ModInt(pow(int(other), self.val, self.mod))
82
83 def __rtruediv__(self, other: Union[int, "ModInt"]) -> "ModInt":
84 return ModInt(int(other) * self._inv(self.val))
85
86 def __eq__(self, other: Union[int, "ModInt"]) -> bool:
87 return self.val == int(other)
88
89 def __lt__(self, other: Union[int, "ModInt"]) -> bool:
90 return self.val < int(other)
91
92 def __le__(self, other: Union[int, "ModInt"]) -> bool:
93 return self.val <= int(other)
94
95 def __gt__(self, other: Union[int, "ModInt"]) -> bool:
96 return self.val > int(other)
97
98 def __ge__(self, other: Union[int, "ModInt"]) -> bool:
99 return self.val >= int(other)
100
101 def __ne__(self, other: Union[int, "ModInt"]) -> bool:
102 return self.val != int(other)
103
104 def __neg__(self) -> "ModInt":
105 return ModInt(-self.val)
106
107 def __pos__(self) -> "ModInt":
108 return ModInt(self.val)
109
110 def __int__(self) -> int:
111 return self.val
112
113 def __str__(self) -> str:
114 return str(self.val)
115
116 def __repr__(self):
117 # return f'ModInt({self})'
118 return f"{self}"