# Fast factorial computation

I'm trying to solve this problem - https://codeforces.com/problemset/problem/711/E

I've already found and proved that the result is equal to: $$1 - \frac{2^n (2^n - 1) \cdots (2 ^ n - k + 1)}{2^{nk}}.$$ Now I need to compute it, and it's hard as $$n$$ and $$k$$ could both be as large as $$10^{18}$$. Computing $$2^{nk}$$ is easy. But I have a problem with this factorial. Result, of course, only need to be found modulo $$10^6 + 3$$.

EDIT:

Note that A and B must be coprime before their remainders modulo $$10^6 + 3$$ are taken.

• If $k \geq 10^6 + 3$ then the answer is simply $1$. Otherwise, compute $a=2^n \bmod 10^6+3$ as usual, and then multiply $a(a-1)\cdots(a-k+1)$, at most $10^6 + 2$ factors. – Yuval Filmus Jan 13 at 18:46
• By the way, I don't see any factorial in this post. – Yuval Filmus Jan 13 at 18:46
• This will probably help you: cp-algorithms.com/algebra/factorial-modulo.html – Dmitry Jan 13 at 19:13
• @Dmitry Not really. If you try to compute $2^n!/(2^n-k)!$, you will just get $0/0$. – Yuval Filmus Jan 14 at 7:53
• The numerator is just $0$ unless $k$ is smaller than the modulus, let's call it $m$. In the latter case, you can multiply the $k<m$ terms modulo $m$ directly. – Emil Jeřábek Jan 14 at 9:03