Function to return a ^ n % mod
static long power ( long a , long n ) { if ( n == 0 ) { return 1 ; } long p = power ( a , n / 2 ) % mod ; p = ( p * p ) % mod ; if ( n == 1 ) { p = ( p * a ) % mod ; } return p ; }