MOD = 10**9 + 7 MOD2 = MOD*MOD - 1 def fib(n, mod) if n < 1 return 0 end a = [[1,1],[1,0]] b = [[1,0],[0,1]] n -= 1 while(n > 0) if n & 1 > 0 b = merge(b, a, mod) end a = merge(a, a, mod) n >>= 1 end b[0][0] end def merge(a, b, mod) _c = [[],[]] 2.times do |i| 2.times do |j| c = 0 2.times do |k| c += a[i][k] * b[k][j] end c %= mod _c[i][j] = c end end return _c end n = gets.to_i puts fib(fib(n, MOD2), MOD)