Modular Arithmetic

The problem

Many counting problems have answers like the number of ways to arrange 1000 items, which has thousands of digits. No integer type holds that. So the statement says: "print the answer modulo $10^9 + 7$", meaning the remainder after dividing by $1\,000\,000\,007$.

The modulus is a prime that fits in 32 bits. Two numbers below it multiply to less than about $10^{18}$, which still fits in a 64-bit long long.

You must keep every number reduced as you go. Computing the exact value first and reducing at the end is the same wrong idea as brute force: the exact value is far too big.