An Exponent Written Out Digit by Digit

A cipher machine needs a ** e mod m, but the exponent e is so long it is delivered as a decimal string e_digits (thousands of digits). Compute the result by processing the digits from left to right; write your own square-and-multiply helper rather than relying on a built-in power function.

Examples

Input:  a = 3, e_digits = "13", m = 100
Output: 23
Explanation: 3**13 = 1594323.

Input:  a = 2, e_digits = "0", m = 7
Output: 1

Constraints

• 0 <= a <= 10**18, 1 <= m <= 10**9 + 7, 1 <= len(e_digits) <= 10**4.
• 0 ** 0 counts as 1; any value mod 1 is 0.
• Target complexity: O(len(e_digits)) modular multiplications.

Goals

• Implement square-and-multiply modular powering
• Consume an exponent given as a decimal string one digit at a time
• Handle a modulus of 1 and an exponent of 0