Here's the recursive breakdown in code:
MOD = 1337
def power(a, n, mod):
result = 1
a = a % mod
while n > 0:
if n % 2 == 1:
result = (result * a) % mod
n = n // 2
a = (a * a) % mod
return result
def superPow(a, b):
if not b:
return 1
last_digit = b[-1]
remaining = b[:-1]
# a^b = (a^remaining)^10 * a^last_digit
part1 = power(superPow(a, remaining), 10, MOD)
part2 = power(a, last_digit, MOD)
return (part1 * part2) % MOD
Each recursive call shrinks by one digit. The base case is when is empty, which returns 1.