Function to compute 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 ) == 1 ) p = ( p * a ) % mod ; return p ; }