1# from titan_pylib.math.mod_int_998244353 import ModInt998244353
2from typing import Union
3
4_titan_pylib_ModInt998244353_MOD = 998244353
5
6
7class ModInt998244353:
8
9 __slots__ = "val"
10
11 @staticmethod
12 def _inv(a: int) -> int:
13 res = a % _titan_pylib_ModInt998244353_MOD
14 a = a * a % _titan_pylib_ModInt998244353_MOD
15 res = res * a % _titan_pylib_ModInt998244353_MOD
16 a = a * a % _titan_pylib_ModInt998244353_MOD
17 res = res * a % _titan_pylib_ModInt998244353_MOD
18 a = a * a % _titan_pylib_ModInt998244353_MOD
19 res = res * a % _titan_pylib_ModInt998244353_MOD
20 a = a * a % _titan_pylib_ModInt998244353_MOD
21 res = res * a % _titan_pylib_ModInt998244353_MOD
22 a = a * a % _titan_pylib_ModInt998244353_MOD
23 res = res * a % _titan_pylib_ModInt998244353_MOD
24 a = a * a % _titan_pylib_ModInt998244353_MOD
25 res = res * a % _titan_pylib_ModInt998244353_MOD
26 a = a * a % _titan_pylib_ModInt998244353_MOD
27 res = res * a % _titan_pylib_ModInt998244353_MOD
28 a = a * a % _titan_pylib_ModInt998244353_MOD
29 res = res * a % _titan_pylib_ModInt998244353_MOD
30 a = a * a % _titan_pylib_ModInt998244353_MOD
31 res = res * a % _titan_pylib_ModInt998244353_MOD
32 a = a * a % _titan_pylib_ModInt998244353_MOD
33 res = res * a % _titan_pylib_ModInt998244353_MOD
34 a = a * a % _titan_pylib_ModInt998244353_MOD
35 res = res * a % _titan_pylib_ModInt998244353_MOD
36 a = a * a % _titan_pylib_ModInt998244353_MOD
37 res = res * a % _titan_pylib_ModInt998244353_MOD
38 a = a * a % _titan_pylib_ModInt998244353_MOD
39 res = res * a % _titan_pylib_ModInt998244353_MOD
40 a = a * a % _titan_pylib_ModInt998244353_MOD
41 res = res * a % _titan_pylib_ModInt998244353_MOD
42 a = a * a % _titan_pylib_ModInt998244353_MOD
43 res = res * a % _titan_pylib_ModInt998244353_MOD
44 a = a * a % _titan_pylib_ModInt998244353_MOD
45 res = res * a % _titan_pylib_ModInt998244353_MOD
46 a = a * a % _titan_pylib_ModInt998244353_MOD
47 res = res * a % _titan_pylib_ModInt998244353_MOD
48 a = a * a % _titan_pylib_ModInt998244353_MOD
49 res = res * a % _titan_pylib_ModInt998244353_MOD
50 a = a * a % _titan_pylib_ModInt998244353_MOD
51 res = res * a % _titan_pylib_ModInt998244353_MOD
52 a = a * a % _titan_pylib_ModInt998244353_MOD
53 res = res * a % _titan_pylib_ModInt998244353_MOD
54 a = a * a % _titan_pylib_ModInt998244353_MOD
55 res = res * a % _titan_pylib_ModInt998244353_MOD
56 a = a * a % _titan_pylib_ModInt998244353_MOD
57 res = res * a % _titan_pylib_ModInt998244353_MOD
58 a = a * a % _titan_pylib_ModInt998244353_MOD
59 a = a * a % _titan_pylib_ModInt998244353_MOD
60 res = res * a % _titan_pylib_ModInt998244353_MOD
61 a = a * a % _titan_pylib_ModInt998244353_MOD
62 res = res * a % _titan_pylib_ModInt998244353_MOD
63 a = a * a % _titan_pylib_ModInt998244353_MOD
64 a = a * a % _titan_pylib_ModInt998244353_MOD
65 res = res * a % _titan_pylib_ModInt998244353_MOD
66 a = a * a % _titan_pylib_ModInt998244353_MOD
67 res = res * a % _titan_pylib_ModInt998244353_MOD
68 a = a * a % _titan_pylib_ModInt998244353_MOD
69 res = res * a % _titan_pylib_ModInt998244353_MOD
70 return res
71
72 @staticmethod
73 def get_mod() -> int:
74 return _titan_pylib_ModInt998244353_MOD
75
76 def __init__(self, val: int) -> None:
77 self.val = (
78 val
79 if 0 <= val < _titan_pylib_ModInt998244353_MOD
80 else val % _titan_pylib_ModInt998244353_MOD
81 )
82
83 def __add__(self, other: Union[int, "ModInt998244353"]) -> "ModInt998244353":
84 return ModInt998244353(self.val + int(other))
85
86 def __sub__(self, other: Union[int, "ModInt998244353"]) -> "ModInt998244353":
87 return ModInt998244353(self.val - int(other))
88
89 def __mul__(self, other: Union[int, "ModInt998244353"]) -> "ModInt998244353":
90 return ModInt998244353(self.val * int(other))
91
92 def __pow__(self, other: Union[int, "ModInt998244353"]) -> "ModInt998244353":
93 return ModInt998244353(
94 pow(self.val, int(other), _titan_pylib_ModInt998244353_MOD)
95 )
96
97 def __truediv__(self, other: Union[int, "ModInt998244353"]) -> "ModInt998244353":
98 return ModInt998244353(self.val * (self._inv(int(other))))
99
100 __iadd__ = __add__
101 __isub__ = __sub__
102 __imul__ = __mul__
103 __ipow__ = __pow__
104 __itruediv__ = __truediv__
105
106 # def __iadd__(self, other: Union[int, 'ModInt998244353']) -> 'ModInt998244353':
107 # self.val += int(other)
108 # self.val %= _titan_pylib_ModInt998244353_MOD
109 # return self
110
111 # def __isub__(self, other: Union[int, 'ModInt998244353']) -> 'ModInt998244353':
112 # self.val -= int(other)
113 # self.val %= _titan_pylib_ModInt998244353_MOD
114 # return self
115
116 # def __imul__(self, other: Union[int, 'ModInt998244353']) -> 'ModInt998244353':
117 # self.val *= int(other)
118 # self.val %= _titan_pylib_ModInt998244353_MOD
119 # return self
120
121 # def __ipow__(self, other: Union[int, 'ModInt998244353']) -> 'ModInt998244353':
122 # self.val = pow(self.val, int(other), _titan_pylib_ModInt998244353_MOD)
123 # return self
124
125 # def __itruediv__(self, other: Union[int, 'ModInt998244353']) -> 'ModInt998244353':
126 # self.val *= self._inv(int(other))
127 # self.val %= _titan_pylib_ModInt998244353_MOD
128 # return self
129
130 __radd__ = __add__
131 __rmul__ = __mul__
132
133 def __rsub__(self, other: Union[int, "ModInt998244353"]) -> "ModInt998244353":
134 return ModInt998244353(int(other) - self.val)
135
136 def __rpow__(self, other: Union[int, "ModInt998244353"]) -> "ModInt998244353":
137 return ModInt998244353(
138 pow(int(other), self.val, _titan_pylib_ModInt998244353_MOD)
139 )
140
141 def __rtruediv__(self, other: Union[int, "ModInt998244353"]) -> "ModInt998244353":
142 return ModInt998244353(int(other) * self._inv(self.val))
143
144 def __eq__(self, other: Union[int, "ModInt998244353"]) -> bool:
145 return self.val == int(other)
146
147 def __lt__(self, other: Union[int, "ModInt998244353"]) -> bool:
148 return self.val < int(other)
149
150 def __le__(self, other: Union[int, "ModInt998244353"]) -> bool:
151 return self.val <= int(other)
152
153 def __gt__(self, other: Union[int, "ModInt998244353"]) -> bool:
154 return self.val > int(other)
155
156 def __ge__(self, other: Union[int, "ModInt998244353"]) -> bool:
157 return self.val >= int(other)
158
159 def __ne__(self, other: Union[int, "ModInt998244353"]) -> bool:
160 return self.val != int(other)
161
162 def __neg__(self) -> "ModInt998244353":
163 return ModInt998244353(-self.val)
164
165 def __pos__(self) -> "ModInt998244353":
166 return ModInt998244353(self.val)
167
168 def __int__(self) -> int:
169 return self.val
170
171 def __str__(self) -> str:
172 return str(self.val)
173
174 def __repr__(self):
175 # return f'ModInt998244353({self})'
176 return f"{self}"