#!/usr/bin/ruby

#
## https://rosettacode.org/wiki/Modular_exponentiation
#

func expmod(a, b, n) {
    var c = 1
    do {
        (c *= a) %= n if b.is_odd
        (a *= a) %= n
    } while (b //= 2)
    c
}

var result = expmod(
    2988348162058574136915891421498819466320163312926952423791023078876139,
    2351399303373464486466122544523690094744975233415544072992656881240319,
    10**40)

assert_eq(result, 1527229998585248450016808958343740453059)
say result