>>336 Ruby
def powmod(n, e, m)
　　case e
　　when 0 then 1
　　when :even?.to_proc then powmod(n * n % m, e >> 1, m)
　　else n * powmod(n, e - 1, m) % m
　　end
end

def kotae(n, m)
　　index, cycle = (1..m).each_with_object([1]) do |i, a|
　　　　x = (a.last * n % m)
　　　　ind = a.index(x)
　　　　ind.nil? ? a.push(x) : (break([ind, i - ind]))
　　end
　　x = n.times.reduce(1){|r, i| r *= n; r < index ? r : break}
　　y = x.nil? ? index + (powmod(n, n, cycle) - index) % cycle : x
　　powmod(n, y, m)
end

[0, 1, 2, 3, 4, 5, 10, 11, 13, 100, 777].each{|i| puts '%d -> %06d' % [i, kotae(i, 10**6)]}
# =>0 -> 000000
1 -> 000001
2 -> 000016
3 -> 484987
4 -> 084096
5 -> 203125
10 -> 000000
11 -> 906611
13 -> 549053
100 -> 000000
777 -> 977097