Modular inverse

For Questions involving big numbers, where you have to print the numbers mod a prime number(such as 1000000007), the following function would come-in handy:





// the function calculated (inverse of a) mod b
LL mul_inv(LL a, LL b)
{
    LL b0 = b, t, q;
    LL x0 = 0, x1 = 1;
    if (b == 1) return 1;
    while (a > 1) {
        q = a / b;
        t = b, b = a % b, a = t;
        t = x0, x0 = x1 - q * x0, x1 = t;
    }
    if (x1 < 0) x1 += b0;
    return x1;
}