Modular Multiplicative Inverse of a when m = 1000000007

modinv_1000000007.c

uint64_t modinv_1000000007(uint64_t a)
{
    a %= 1000000007;
    uint64_t r = a;
    a = (a * a) % 1000000007;
    a = (a * a) % 1000000007;
    r = (r * a) % 1000000007;
    a = (a * a) % 1000000007;
    a = (a * a) % 1000000007;
    a = (a * a) % 1000000007;
    a = (a * a) % 1000000007;
    a = (a * a) % 1000000007;
    a = (a * a) % 1000000007;
    a = (a * a) % 1000000007;
    r = (r * a) % 1000000007;
    a = (a * a) % 1000000007;
    a = (a * a) % 1000000007;
    r = (r * a) % 1000000007;
    a = (a * a) % 1000000007;
    a = (a * a) % 1000000007;
    a = (a * a) % 1000000007;
    r = (r * a) % 1000000007;
    a = (a * a) % 1000000007;
    r = (r * a) % 1000000007;
    a = (a * a) % 1000000007;
    a = (a * a) % 1000000007;
    r = (r * a) % 1000000007;
    a = (a * a) % 1000000007;
    a = (a * a) % 1000000007;
    r = (r * a) % 1000000007;
    a = (a * a) % 1000000007;
    r = (r * a) % 1000000007;
    a = (a * a) % 1000000007;
    a = (a * a) % 1000000007;
    a = (a * a) % 1000000007;
    r = (r * a) % 1000000007;
    a = (a * a) % 1000000007;
    r = (r * a) % 1000000007;
    a = (a * a) % 1000000007;
    r = (r * a) % 1000000007;
    a = (a * a) % 1000000007;
    a = (a * a) % 1000000007;
    r = (r * a) % 1000000007;
    a = (a * a) % 1000000007;
    r = (r * a) % 1000000007;
    a = (a * a) % 1000000007;
    return (r * a) % 1000000007;
}