2D array to store value of combinations nCr
ll C [ max - 1 ] [ max - 1 ] ; ll power ( ll x , unsigned ll y ) { unsigned ll res = 1 ; x = x % MOD ; while ( y > 0 ) { if ( y & 1 ) { res = ( res * x ) % MOD ; } y = y >> 1 ; x = ( x * x ) % MOD ; } return res % MOD ; }