using System;
using System.Collections.Generic;
using RedCorona.Utils;

class Fibonacci{
 public static LargeInteger GetFib(long n){
  double p = Math.Sqrt(5);
  bool negative = n < 0;
  if(negative) n = -n;
  uint e = (uint)n;
  LargeInteger res;
  if(n > 4294967295) res = GetFibIter(n);
  else res = (1 / Math.Sqrt(5)) * (((LargeInteger)((p + 1) / 2)).Power(e) - ((LargeInteger)(2 / (p + 1))).Power(e) * (2 * -(e % 2)) / 2);
  if(negative && n % 2 == 0) res = -res;
  string t = res.ToLongString();
  int i = t.IndexOf(".");
  char r = t[i + 1];
  t = t.Substring(0, i).Replace(",", null);
  res = LargeInteger.Parse(t);
  if(r > '4') res += 1;
  return res;
 }

 public static double GetFibDouble(double n){
  double p = Math.Sqrt(5);
  bool round = n == Math.Round(n);
  double res = (1 / p) * (Math.Pow((p + 1) / 2, n) - Math.Pow(2 / (p + 1), n) * Math.Cos(n * Math.PI));
  if(round) res = Math.Round(res);
  return res;
 }

 private static List<LargeInteger> BigFibs = new List<LargeInteger>();


 private static LargeInteger GetFibIter(LargeInteger n){
  if(BigFibs.Count > n - 4294967294) return BigFibs[(n - 4294967294).IntegerValue];
  if(BigFibs.Count == 0){
   BigFibs.Add(GetFib(4294967294));
   BigFibs.Add(GetFib(4294967295));
  }
  LargeInteger res = 0;
  for(LargeInteger i = 4294967295; i < n; i += 1){
   res = BigFibs[(i - 4294967295).IntegerValue] + BigFibs[(i - 4294967294).IntegerValue];
   BigFibs.Add(res);
  }
  return res;
 }
}

class AltFibonacci{
 public static LargeInteger AltGetFib(int n){
  LargeInteger p = Math.Sqrt(5);
  Double i = 1/Math.Sqrt(5);
  return(((p + 1).Power(n) - (p - 1).Power(n)) / (((LargeInteger)2).Power(n) * p));
 }

 public static double AltGetFibDouble(int n){
  double p = Math.Sqrt(5);
  return(Math.Round((Math.Pow(1 + p, (double)n) - Math.Pow(1 - p, (double)n)) / (Math.Pow(2, (double)n) * p)));
 }
}

class FibTest{
 public static void Main(){
  for(long i = -1480; i < -1470 ; ++i){
   Console.WriteLine("fib({0})", i);
   Console.WriteLine(" {0}", Fibonacci.GetFibDouble(i));
   Console.WriteLine(" {0}", Fibonacci.GetFib(i));
  }
 }
}