gistfile1.rb

#!/usr/bin/env ruby

$memo = [1]

JUMAN = 100000

def removeZeros(x)
        while (x % 10 == 0) do
                x /= 10
        end
        return x
end

def f(n)
        return $memo[n] if (n < $memo.length)
        if (n < JUMAN) then
                x = 1
                1.upto(n) do |i|
                        x *= i
                        x = removeZeros(x)
                        x %= JUMAN
                        $memo[i] = x
                end
                return x
        elsif (n >= JUMAN) then
                m = (n / JUMAN).to_i
                n %= JUMAN
                x = f(JUMAN - 1) # equals to f(JUMAN), by definition.
                x = g(x, m) # equals to (removeZeros(x ** m) % JUMAN).
                x *= f(n)
                return removeZeros(x) % JUMAN
        end
end

def g(x, m)
        # g(x, m) should calculate (removeZeros(x ** m) % JUMAN).
        if (m == 0) then
                return 1
        elsif (m % 2 == 1) then
                return removeZeros(x * (g(x, (m - 1) / 2) ** 2)) % JUMAN
        else
                return removeZeros(g(x, m / 2) ** 2) % JUMAN
        end
end

https://twitter.com/c_nk1/statuses/347673982486597632?tw_i=347673982486597632&tw_e=details&tw_p=twt
https://twitter.com/math_neko/status/347679862519115776
https://github.com/shiracha/hironoproblem