How to calculate $2^{mn-1}/(2^n-1) \bmod{(10^9+7)}$

Question

I was trying to solve Magical Five problem on codeforces. I have correctly formed an equation which I need to solve via program such that resulting number don't overflow. Answer can be Python or C++ specific.

Now, the equation is:

$$\frac{2^{mn-1}}{2^n-1} \bmod{p} \qquad \text{where $p=10^9+7$ is prime}$$

I know denominator divides numerator evenly but I am not able to prove this from this equation.

PS: I know my equation is correct as I have matched my solution against the provided editorial at Solution Page

PPS: I have also read about Fermat's little theorem, which states that $a^p \equiv a \bmod{p}$ where $p$ is prime and $a < p$.

Answer 1

Since for the given range, $2^N - 1$ cannot be a multiple of $p = 10^9 + 7$, you can obtain the result by modular multiplication with the inverse of $2^N - 1$ modulo $p$.

Compute $r = 2^N \pmod{p}$, via exponentiation by repeated squaring, for example (simple to implement, and quite fast). Compute $s = r^M \pmod{p}$, with the same algorithm. Find the modular inverse of $r-1$, for example with the extended Euclidean algorithm. Compute $(s-1)\cdot(r-1)^{-1} \pmod{p}$.

All computations can be done without overflow using a 64-bit integer type.

uint64_t mod_pow(uint64_t base, uint64_t exponent) {
    uint64_t result = 1;
    while(exponent) {
       if (exponent % 2 != 0) {
           result *= base;
           result %= p;
       }
       base *= base;
       base %= p;
       exponent /= 2;
    }
    return result;
}

uint64_t mod_inv(uint64_t num, uint64_t mod) {
    uint64_t m = mod, k = num, pn = 1, po = 0, q, r;
    bool flip = false;
    while(k > 0) {
        q = m / k;
        r = m % k;
        m = k;
        k = r;
        r = q*pn + po;
        po = pn;
        pn = r;
        flip = !flip;
    }
    return flip ? po : mod - po;
}

Answer 2

With great help from Daniel, I have been able to solve this problem. I just wanted to add some additional info via this answer.

Let me reduce the exact equation to A/B mod p where A and B can be quite large numbers. Or (A%p * (1/B %p))%p

Since p is prime, we have some hint here that gcd(B,p) is 1 which means B and p are co-prime.

Let us assume C is the modular inverse of B, then our new equation becomes ((A%p) * (C%p))%p because BC ≡ 1 (mod p) so C ≡ 1/B (mod p)

Since p is prime, we can use Euler theorem to say:

B^F(p) ≡ 1 (mod p) where F(p) is totient function and F(p): number of terms less than p which are coprime to p.

When p is prime, F(p) = p-1

B^(p-1) ≡ 1 (mod p)

B^(p-2) ≡ 1/B (mod p) // Dividing by B on both sides

Hence our final equation becomes:

A * B^(p-2) mod p which can be solved easily now :D