mod1 = 10**9 + 7 mod2 = 101010101010101010101 n = gets.to_i if n == 1 then puts 0 else m = n n = m-1 res = [1,0,0,1] mat = [100,1,0,1] while n != 0 do if( n%2 == 1 ) then res = [ mat[0] * res[0] + mat[1] * res[2], mat[0] * res[1] + mat[1] * res[3], mat[2] * res[0] + mat[3] * res[2], mat[2] * res[1] + mat[3] * res[3] ] res = res.map{|x| x % mod1 } end mat = [ mat[0] * mat[0] + mat[1] * mat[2], mat[0] * mat[1] + mat[1] * mat[3], mat[2] * mat[0] + mat[3] * mat[2], mat[2] * mat[1] + mat[3] * mat[3] ] mat = mat.map{|x| x%mod1 } n /= 2 end puts (res[0] + res[1]) % mod1 n = m-1 res = [1,0,0,1] mat = [100,1,0,1] while n != 0 do if( n%2 == 1 ) then res = [ mat[0] * res[0] + mat[1] * res[2], mat[0] * res[1] + mat[1] * res[3], mat[2] * res[0] + mat[3] * res[2], mat[2] * res[1] + mat[3] * res[3] ] res = res.map{|x| x % mod2 } end mat = [ mat[0] * mat[0] + mat[1] * mat[2], mat[0] * mat[1] + mat[1] * mat[3], mat[2] * mat[0] + mat[3] * mat[2], mat[2] * mat[1] + mat[3] * mat[3] ] mat = mat.map{|x| x%mod2 } n /= 2 end puts (res[0] + res[1]) % mod2 end