Modulo power for large numbers represented as strings | Python3 program to find ( a ^ b ) % MOD where a and b may be very large and represented as strings . ; Returns modulo exponentiation for two numbers represented as long long int . It is used by powerStrings ( ) . Its complexity is log ( n ) ; Returns modulo exponentiation for two numbers represented as strings . It is used by powerStrings ( ) ; We convert strings to number ; calculating a % MOD ; calculating b % ( MOD - 1 ) ; Now a and b are long long int . We calculate a ^ b using modulo exponentiation ; As numbers are very large that is it may contains upto 10 ^ 6 digits . So , we use string .
MOD = 1000000007 ; NEW_LINE def powerLL ( x , n ) : NEW_LINE INDENT result = 1 ; NEW_LINE while ( n ) : NEW_LINE INDENT if ( n & 1 ) : NEW_LINE INDENT result = result * x % MOD ; NEW_LINE DEDENT n = int ( n / 2 ) ; NEW_LINE x = x * x % MOD ; NEW_LINE DEDENT return result ; NEW_LINE DEDENT def powerStrings ( sa , sb ) : NEW_LINE INDENT a = 0 ; NEW_LINE b = 0 ; NEW_LINE for i in range ( len ( sa ) ) : NEW_LINE INDENT a = ( a * 10 + ( ord ( sa [ i ] ) - ord ( '0' ) ) ) % MOD ; NEW_LINE DEDENT for i in range ( len ( sb ) ) : NEW_LINE INDENT b = ( b * 10 + ( ord ( sb [ i ] ) - ord ( '0' ) ) ) % ( MOD - 1 ) ; NEW_LINE DEDENT return powerLL ( a , b ) ; NEW_LINE DEDENT sa = "2" ; NEW_LINE sb = "3" ; NEW_LINE print ( powerStrings ( sa , sb ) ) ; NEW_LINE