Modular multiplication to avoid the overflow of multiplication Please see below for details https : www . geeksforgeeks . org / how - to - avoid - overflow - in - modular - multiplication /
def modMult ( a , b , mod ) : NEW_LINE INDENT res = 0 NEW_LINE a = a % mod NEW_LINE while ( b > 0 ) : NEW_LINE INDENT if ( b % 2 == 1 ) : NEW_LINE INDENT res = ( res + a ) % mod NEW_LINE DEDENT a = ( a * 2 ) % mod NEW_LINE b //= 2 NEW_LINE DEDENT return res % mod NEW_LINE DEDENT