Your task is to calculate ab mod 1337 where a is a positive integer and b is an extremely large positive integer given in the form of an array.
Example1:
a = 2
b = [3] Result: 8
Example2:
a = 2
b = [1,0] Result: 1024
使用公式 c = ab => c mod d = [a mod d * b mod d] mod d
所以a^423 mod d = (a^100)^4 * (a ^10)^2 * a^3
class Solution(object):
def superPow(self, a, b):
"""
:type a: int
:type b: List[int]
:rtype: int
"""
ans = 1
mod = 1337
for i in b[::-1]:
ans = ans * a ** i % mod
a = a ** 10 % mod
return ans % mod