constexpr ll mod = 1'000'000'009;

ll binomPPow(ll n, ll k, ll p) {
	ll res = 1;
	if (p > n) {
	} else if (p > n - k || (p * p > n && n % p < k % p)) {
		res *= p;
		res %= mod;
	} else if (p * p <= n) {
		ll c = 0, tmpN = n, tmpK = k;
		while (tmpN > 0) {
			if (tmpN % p < tmpK % p + c) {
				res *= p;
				res %= mod;
				c = 1;
			} else c = 0;
			tmpN /= p;
			tmpK /= p;
	}}
	return res;
}

ll calc_binom(ll n, ll k) {
	if (k > n) return 0;
	ll res = 1;
	k = min(k, n - k);
	for (ll i = 0; primes[i] <= n; i++) {
		res *= binomPPow(n, k, primes[i]);
		res %= mod;
	}
	return res;
}
' alt='cgit logo'/></a></td>
<td class='main'><a href='/'>index</a> : <a href='/tcr/'>tcr</a></td><td class='form'><form method='get'>
<input type='hidden' name='id' value='efb8d8c9c45d3d50acbc6a96e8ab73041758b066'/><select name='h' onchange='this.form.submit();'>
<option value='master' selected='selected'>master</option>
</select> <input type='submit' value='switch'/></form></td></tr>
<tr><td class='sub'>Team Contest Reference
</td><td class='sub right'></td></tr></table>
<table class='tabs'><tr><td>
<a href='/tcr/'>summary</a><a href='/tcr/refs/?id=efb8d8c9c45d3d50acbc6a96e8ab73041758b066'>refs</a><a href='/tcr/log/math/multInv.cpp'>log</a><a class='active' href='/tcr/tree/math/multInv.cpp?id=efb8d8c9c45d3d50acbc6a96e8ab73041758b066'>tree</a><a href='/tcr/commit/math/multInv.cpp?id=efb8d8c9c45d3d50acbc6a96e8ab73041758b066'>commit</a><a href='/tcr/diff/math/multInv.cpp?id=efb8d8c9c45d3d50acbc6a96e8ab73041758b066'>diff</a></td><td class='form'><form class='right' method='get' action='/tcr/log/math/multInv.cpp'>
<input type='hidden' name='id' value='efb8d8c9c45d3d50acbc6a96e8ab73041758b066'/><select name='qt'>
<option value='grep'>log msg</option>
<option value='author'>author</option>
<option value='committer'>committer</option>
<option value='range'>range</option>
</select>
<input class='txt' type='search' size='10' name='q' value=''/>
<input type='submit' value='search'/>
</form>
</td></tr></table>
<div class='path'>path: <a href='/tcr/tree/?id=efb8d8c9c45d3d50acbc6a96e8ab73041758b066'>root</a>/<a href='/tcr/tree/math?id=efb8d8c9c45d3d50acbc6a96e8ab73041758b066'>math</a>/<a href='/tcr/tree/math/multInv.cpp?id=efb8d8c9c45d3d50acbc6a96e8ab73041758b066'>multInv.cpp</a></div><div class='content'>blob: 87603f32b0af1dfc44be5b47f90aefb1bc375c90 (<a href='/tcr/plain/math/multInv.cpp?id=efb8d8c9c45d3d50acbc6a96e8ab73041758b066'>plain</a>)
<table summary='blob content' class='blob'>
<tr><td class='linenumbers'><pre><a id='n1' href='#n1'>1</a>
<a id='n2' href='#n2'>2</a>
<a id='n3' href='#n3'>3</a>
<a id='n4' href='#n4'>4</a>
<a id='n5' href='#n5'>5</a>
</pre></td>
<td class='lines'><pre><code>