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