#include <iostream>
 
/*
 * Bartosz "WiedźMAC" Bednarczyk
 * Liceum Ogólnokształcące im. Władysława Broniewskiego w Strzelcach Opolskich
 * Obliczanie interacyjnie elementu ciągu fibonacciego dla dużych liczb  
 * www.algorytm.org
 */
 
inline int Cyfra( char znak )  { return int(znak-48);    }      // Funckcja zamieniająca znak na cyfrę
 
inline char Znak( int Liczba ) { return char(Liczba+48); }      // Funkcja zamieniająca cyfrę na znak
 
std::string Dodawanie( std::string &A, std::string &B )
{     
       while( A.length() != B.length() )        // Porównywanie długości stringów
       {
              if( A.length() > B.length() )     // Jeżeli któryś z nich jest mniejszy to dodajemy zera
              {
                   B = "0" + B;
              }
              else A = "0" + A;
       }
       
       std::string Wynik = "";  // Wynik dodawania
       int Pomocnicza = 0;      // Zmienna pomocnicza
       
       for(int i = A.length()-1; i >= 0; i-- )  // Właściwa procedura dodawania
        {
               int Pom = Cyfra(A[i]) + Cyfra(B[i]) + Pomocnicza;        // Obliczamy sumę kolejnych cyfr ciągu
               Wynik = Znak( Pom % 10 ) + Wynik;                        // Zapisujemy ją do zmiennej Wynik
               Pomocnicza = int(Pom/10);
       }
       
       if( Pomocnicza != 0 ) Wynik = Znak( Pomocnicza ) + Wynik;        // Jeżeli coś zostało, to dodajemy na początek
       
       return Wynik;
}
 
int main()
{
        std::ios_base::sync_with_stdio(false);    // Przyśpieszenie I/O
        
        std::string Fib0 = "0", Fib1 = "1", FibN;       // Elementy ciągu Fibonacciego
        
        unsigned long long int N, i;    
        
        std::cout << "Ktory element ciagu obliczyc?\n";
        std::cin >> N;
        
        if( N < 2 )
        {
                if( N == 0 ) FibN = Fib0;
                else FibN = Fib1;
        }
        else
        {
                for( i = 2; i <= N; i++ )       // Obliczanie elementu ciągu fibonacciego
                {
                        FibN = Dodawanie( Fib0, Fib1 );
                        Fib0 = Fib1;
                        Fib1 = FibN;
                }
        }
        
        std::cout << "Fib(" << N << ") = " << FibN << "\n";     // Wypisywanie wyniku
        
        return 0;
}