FastExponentiation.swift

import Foundation

let mod = 10000000 // 10e7

func fastPow(base: Int, power: Int, mod: Int = mod) -> Int {
    // Base cases
    if base == 0 {
        return 0
    } else if power == 0 {
        return 1
    }
    
    // Recursion
    if power % 2 == 0 {
        let half = fastPow(base: base, power: power / 2) % mod
        return (half * half) % mod
    } else {
        let result = fastPow(base: base, power: power - 1, mod: mod) % mod
        return (base * result) % mod
    }
}

fastPow(base: 10, power: 10) // 0
fastPow(base: 10, power: 100000) // 0
fastPow(base: 2, power: 10000) // 6709376
fastPow(base: 2, power: 10000001) // 4218752
fastPow(base: 3, power: 7000000) // 1