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