1# from titan_pylib.math.mod_array import ModArray
2from typing import Iterable, Union
3from functools import reduce, lru_cache
4
5
6class ModArray998244353:
7
8 @staticmethod
9 @lru_cache(maxsize=None)
10 def _inv(a: int) -> int:
11 res = 1
12 b = 998244351
13 while b:
14 if b & 1:
15 res = res * a % 998244353
16 a = a * a % 998244353
17 b >>= 1
18 return res
19
20 def __init__(self, n_or_a: Union[int, Iterable[int]], e: int = 0):
21 e %= 998244353
22 self.a: list[int] = (
23 [e] * n_or_a if isinstance(n_or_a, int) else [e % 998244353 for e in n_or_a]
24 )
25
26 def resize(self, size: int, e: int = 0):
27 e %= 998244353
28 self.a = [e] * size
29
30 def append(self, v: int) -> None:
31 self.a.append(v % 998244353)
32
33 def pop(self, k: int = -1) -> int:
34 return self.a.pop(k)
35
36 def all_sum(self) -> int:
37 return sum(self.a) % 998244353
38
39 def all_mul(self) -> int:
40 return reduce(lambda x, y: x * y % 998244353, self.a)
41
42 def add(self, k: int, v: int) -> None:
43 self.a[k] = (self.a[k] + v) % 998244353
44
45 def sub(self, k: int, v: int) -> None:
46 self.a[k] = (self.a[k] - v) % 998244353
47
48 def mul(self, k: int, v: int) -> None:
49 self.a[k] = (self.a[k] * v) % 998244353
50
51 def div(self, k: int, v: int) -> None:
52 self.a[k] = (self.a[k] * self._inv(v)) % 998244353
53
54 def get_mod(self) -> int:
55 return 998244353
56
57 def __iter__(self):
58 self._iter = 0
59 return self
60
61 def __next__(self):
62 if self._iter >= len(self.a):
63 raise StopIteration
64 self._iter += 1
65 return self.a[self._iter - 1]
66
67 def __getitem__(self, k: Union[int, slice]) -> Union[int, "ModArray998244353"]:
68 return ModArray998244353(self.a[k]) if isinstance(k, slice) else self.a[k]
69
70 def __setitem__(self, k: int, v: int) -> None:
71 assert isinstance(v, int)
72 self.a[k] = v % 998244353
73
74 def __str__(self):
75 return str(self.a)
76
77 def __len__(self):
78 return len(self.a)
79
80
81Array = ModArray998244353
82
83# ---------------------- #
84
85from typing import Iterable, Union
86from functools import reduce, lru_cache
87
88
89class ModArray1000000007:
90
91 @staticmethod
92 @lru_cache(maxsize=None)
93 def _inv(a: int) -> int:
94 res = 1
95 b = 1000000005
96 while b:
97 if b & 1:
98 res = res * a % 1000000007
99 a = a * a % 1000000007
100 b >>= 1
101 return res
102
103 def __init__(self, n_or_a: Union[int, Iterable[int]], e: int = 0):
104 e %= 1000000007
105 self.a: list[int] = (
106 [e] * n_or_a
107 if isinstance(n_or_a, int)
108 else [e % 1000000007 for e in n_or_a]
109 )
110
111 def resize(self, size: int, e: int = 0):
112 e %= 1000000007
113 self.a = [e] * size
114
115 def append(self, v: int) -> None:
116 self.a.append(v % 1000000007)
117
118 def pop(self, k: int = -1) -> int:
119 return self.a.pop(k)
120
121 def all_sum(self) -> int:
122 return sum(self.a) % 1000000007
123
124 def all_mul(self) -> int:
125 return reduce(lambda x, y: x * y % 1000000007, self.a)
126
127 def add(self, k: int, v: int) -> None:
128 self.a[k] = (self.a[k] + v) % 1000000007
129
130 def sub(self, k: int, v: int) -> None:
131 self.a[k] = (self.a[k] - v) % 1000000007
132
133 def mul(self, k: int, v: int) -> None:
134 self.a[k] = (self.a[k] * v) % 1000000007
135
136 def div(self, k: int, v: int) -> None:
137 self.a[k] = (self.a[k] * self._inv(v)) % 1000000007
138
139 def get_mod(self) -> int:
140 return 1000000007
141
142 def __iter__(self):
143 self._iter = 0
144 return self
145
146 def __next__(self):
147 if self._iter >= len(self.a):
148 raise StopIteration
149 self._iter += 1
150 return self.a[self._iter - 1]
151
152 def __getitem__(self, k: Union[int, slice]) -> Union[int, "ModArray1000000007"]:
153 return ModArray1000000007(self.a[k]) if isinstance(k, slice) else self.a[k]
154
155 def __setitem__(self, k: int, v: int) -> None:
156 assert isinstance(v, int)
157 self.a[k] = v % 1000000007
158
159 def __str__(self):
160 return str(self.a)
161
162 def __len__(self):
163 return len(self.a)
164
165
166Array = ModArray1000000007
167
168# ---------------------- #
169
170from typing import Iterable, Union
171from functools import reduce, lru_cache
172
173
174class ModArray:
175
176 @lru_cache(maxsize=None)
177 def _inv(self, a: int) -> int:
178 res = 1
179 b = self.mod - 2
180 while b:
181 if b & 1:
182 res = res * a % self.mod
183 a = a * a % self.mod
184 b >>= 1
185 return res
186
187 def __init__(self, mod: int, n_or_a: Union[int, Iterable[int]] = [], e: int = 0):
188 self.mod: int = mod
189 e %= mod
190 self.a: list[int] = (
191 [e] * n_or_a if isinstance(n_or_a, int) else [e % mod for e in n_or_a]
192 )
193
194 def resize(self, size: int, e: int = 0):
195 e %= self.mod
196 self.a = [e] * size
197
198 def append(self, v: int) -> None:
199 self.a.append(v % self.mod)
200
201 def pop(self, k: int = -1) -> int:
202 return self.a.pop(k)
203
204 def all_sum(self) -> int:
205 return sum(self.a) % self.mod
206
207 def all_mul(self) -> int:
208 return reduce(lambda x, y: x * y % self.mod, self.a)
209
210 def add(self, k: int, v: int) -> None:
211 self.a[k] = (self.a[k] + v) % self.mod
212
213 def sub(self, k: int, v: int) -> None:
214 self.a[k] = (self.a[k] - v) % self.mod
215
216 def mul(self, k: int, v: int) -> None:
217 self.a[k] = (self.a[k] * v) % self.mod
218
219 def div(self, k: int, v: int) -> None:
220 self.a[k] = (self.a[k] * self._inv(v)) % self.mod
221
222 def get_mod(self) -> int:
223 return self.mod
224
225 def __iter__(self):
226 self._iter = 0
227 return self
228
229 def __next__(self):
230 if self._iter >= len(self.a):
231 raise StopIteration
232 self._iter += 1
233 return self.a[self._iter - 1]
234
235 def __getitem__(self, k: Union[int, slice]) -> Union[int, "ModArray"]:
236 return ModArray(self.mod, self.a[k]) if isinstance(k, slice) else self.a[k]
237
238 def __setitem__(self, k: int, v: int) -> None:
239 assert isinstance(v, int)
240 self.a[k] = v % self.mod
241
242 def __str__(self):
243 return str(self.a)
244
245 def __len__(self):
246 return len(self.a)
247
248
249Array = ModArray
250
251# ---------------------- #