computing ( a ^ b ) % c
static long modpow ( long base1 , long exp , long modulus ) { base1 %= modulus ; long result = 1 ; while ( exp > 0 ) { if ( ( exp & 1 ) > 0 ) result = ( result * base1 ) % modulus ; base1 = ( base1 * base1 ) % modulus ; exp >>= 1 ; } return result ; }