# -*- coding: utf-8 -*-
# http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2048
# 
# 冪剰余の問題.
# http://ja.wikipedia.org/wiki/%E5%86%AA%E5%89%B0%E4%BD%99
#
# b ** e を m で割った余りは以下の関数で効率的に計算できる．
def modpow(b, e, m)
  c = 1
  while e > 0
    if (e & 1) == 1
      c = c * b % m
    end
    e = e >> 1
    b = b * b % m
  end
  c
end
# 最後の10桁とは，10 ** 10 で割った余りのことであり，
# 総和の最後の10桁は，途中の計算の最後の10桁より上の桁には依存しないので，
# 各項の i ** i を 10 ** 10 で割った余りを総和し，
# 最後にさらに10 ** 10 で割った余りを計算する．
puts (1 .. 1000).reduce(0){|sum, i| sum + modpow(i, i, 10 ** 10) } % 10 ** 10