Find remainder when a number A raised to N factorial is divided by P | Function to calculate ( A ^ N ! ) % P in O ( log y ) ; Initialize result ; Update x if it is more than or Equal to p ; In case x is divisible by p ; If y is odd , multiply x with result ; y must be even now ; Returning modular power ; Function to calculate resultant remainder ; Initializing ans to store final remainder ; Calculating remainder ; Returning resultant remainder ; Given input ; Function Call
def power ( x , y , p ) : NEW_LINE INDENT res = 1 NEW_LINE x = x % p NEW_LINE if ( x == 0 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT while ( y > 0 ) : NEW_LINE INDENT if ( y & 1 ) : NEW_LINE INDENT res = ( res * x ) % p NEW_LINE DEDENT y = y >> 1 NEW_LINE x = ( x * x ) % p NEW_LINE DEDENT return res NEW_LINE DEDENT def remainder ( n , a , p ) : NEW_LINE INDENT ans = a % p NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT ans = power ( ans , i , p ) NEW_LINE DEDENT return ans NEW_LINE DEDENT A = 2 NEW_LINE N = 1 NEW_LINE P = 2 NEW_LINE print ( remainder ( N , A , P ) ) NEW_LINE