1# from titan_pylib.math.mod_comb import ModComb
2class ModComb998244353:
3
4 # nCr2のみをつかうときなどは、limit=-1とかにすると吉
5 def __init__(self, limit: int):
6 n = max(1, limit) + 1
7 fact = [0] * n
8 factinv = [0] * n
9 inv = [0] * n
10 fact[0] = 1
11 fact[1] = 1
12 factinv[0] = 1
13 factinv[1] = 1
14 inv[1] = 1
15 for i in range(2, limit + 1):
16 fact[i] = fact[i - 1] * i % 998244353
17 inv[i] = -inv[998244353 % i] * (998244353 // i) % 998244353
18 factinv[i] = factinv[i - 1] * inv[i] % 998244353
19 self._fact = fact
20 self._factinv = factinv
21 self._inv = inv
22 self._limit = limit
23
24 def nPr(self, n: int, r: int) -> int:
25 if r < 0 or n < r:
26 return 0
27 return self._fact[n] * self._factinv[n - r] % 998244353
28
29 def nCr(self, n: int, r: int) -> int:
30 if r < 0 or n < r:
31 return 0
32 return (
33 (self._fact[n] * self._factinv[r] % 998244353)
34 * self._factinv[n - r]
35 % 998244353
36 )
37
38 def nHr(self, n: int, r: int) -> int:
39 return self.nCr(n + r - 1, n - 1)
40
41 def nCr2(self, n: int, r: int) -> int:
42 ret = 1
43 if r > n - r:
44 r = n - r
45 for i in range(r):
46 ret *= n - i
47 ret %= 998244353
48 for i in range(1, r + 1):
49 ret *= pow(i, 998244351, 998244353)
50 ret %= 998244353
51 return ret
52
53
54class ModComb:
55
56 # nCr2のみをつかうときなどは、limit=-1とかにすると吉
57 def __init__(self, limit: int, mod: int):
58 n = max(1, limit) + 1
59 fact = [0] * n
60 factinv = [0] * n
61 inv = [0] * n
62 fact[0] = 1
63 fact[1] = 1
64 factinv[0] = 1
65 factinv[1] = 1
66 inv[1] = 1
67 for i in range(2, limit + 1):
68 fact[i] = fact[i - 1] * i % mod
69 inv[i] = -inv[mod % i] * (mod // i) % mod
70 factinv[i] = factinv[i - 1] * inv[i] % mod
71 self._fact = fact
72 self._factinv = factinv
73 self._inv = inv
74 self._limit = limit
75 self._mod = mod
76
77 def nPr(self, n: int, r: int) -> int:
78 if r < 0 or n < r:
79 return 0
80 return self._fact[n] * self._factinv[n - r] % self._mod
81
82 def nCr(self, n: int, r: int) -> int:
83 if r < 0 or n < r:
84 return 0
85 return (
86 (self._fact[n] * self._factinv[r] % self._mod)
87 * self._factinv[n - r]
88 % self._mod
89 )
90
91 def nHr(self, n: int, r: int) -> int:
92 return self.nCr(n + r - 1, n - 1)
93
94 def nCr2(self, n: int, r: int) -> int:
95 ret = 1
96 if r > n - r:
97 r = n - r
98 for i in range(r):
99 ret *= n - i
100 ret %= self._mod
101 for i in range(1, r + 1):
102 ret *= pow(i, self._mod - 2, self._mod)
103 ret %= self._mod
104 return ret
105
106
107class ModComb1000000007:
108
109 # nCr2のみをつかうときなどは、limit=-1とかにすると吉
110 def __init__(self, limit: int):
111 n = max(1, limit) + 1
112 fact = [0] * n
113 factinv = [0] * n
114 inv = [0] * n
115 fact[0] = 1
116 fact[1] = 1
117 factinv[0] = 1
118 factinv[1] = 1
119 inv[1] = 1
120 for i in range(2, limit + 1):
121 fact[i] = fact[i - 1] * i % 1000000007
122 inv[i] = -inv[1000000007 % i] * (1000000007 // i) % 1000000007
123 factinv[i] = factinv[i - 1] * inv[i] % 1000000007
124 self._fact = fact
125 self._factinv = factinv
126 self._inv = inv
127 self._limit = limit
128
129 def nPr(self, n: int, r: int) -> int:
130 if r < 0 or n < r:
131 return 0
132 return self._fact[n] * self._factinv[n - r] % 1000000007
133
134 def nCr(self, n: int, r: int) -> int:
135 if r < 0 or n < r:
136 return 0
137 return (
138 (self._fact[n] * self._factinv[r] % 1000000007)
139 * self._factinv[n - r]
140 % 1000000007
141 )
142
143 def nHr(self, n: int, r: int) -> int:
144 return self.nCr(n + r - 1, n - 1)
145
146 def nCr2(self, n: int, r: int) -> int:
147 ret = 1
148 if r > n - r:
149 r = n - r
150 for i in range(r):
151 ret *= n - i
152 ret %= 1000000007
153 for i in range(1, r + 1):
154 ret *= pow(i, 1000000005, 1000000007)
155 ret %= 1000000007
156 return ret