# -*- coding: utf-8 -*-
# http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2025
#
require 'bigdecimal'
require 'bigdecimal/math'

# BigDecimalによるビネの公式の逆関数．
def fib_inv(n, prec = 100)
  n = BigDecimal.new(n.to_s)
  phi = BigDecimal.new(((1.0 + Math.sqrt(5.0)) / 2.0).to_s)
  a = BigDecimal.new(Math.sqrt(5.0).to_s)
  n = n.sub(BigDecimal.new(0.5.to_s), prec)
  a = a.mult(n, prec)
  a = BigMath.log(a, prec)
  phi = BigMath.log(phi, prec)
  a = a.div(phi, prec)
  a.to_i + 1
end
# 1000桁を超える最初のフィボナッチ数の項．
puts fib_inv((10 ** (1000 - 1)))