(base, power, mod)
| 1 | def modularExponential(base, power, mod): |
| 2 | if power < 0: |
| 3 | return -1 |
| 4 | base %= mod |
| 5 | result = 1 |
| 6 | |
| 7 | while power > 0: |
| 8 | if power & 1: |
| 9 | result = (result * base) % mod |
| 10 | power = power >> 1 |
| 11 | base = (base * base) % mod |
| 12 | return result |
| 13 | |
| 14 | |
| 15 | def main(): |