modpow

gistfile1.c

//a^b mod m
long long modpow(long long a, long long b, long long m) {
    long long ret = 1; 
    long long mul = a;
    for ( ; b > 0; b = b >> 1) {
        if ( b&1 ) { 
            ret = (ret * mul) % m;
        }   
        mul = (mul * mul) % m;
    }   
    return ret;
}