207. Последовательность из 0 и 1

/********************
* Problem: -.
* Theme: Ukrainian 3 stage 2017 - 1
*/
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define mp make_pair
#define pb push_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i=(a);i>=(b);i--)
#define SZ(A) A.size()
#define f first
#define s second

typedef vector<int> VI;
typedef vector<pair<int,int> > VII;
typedef pair<int,int> pii;
typedef pair<int,pair<int,int> > pip;
typedef pair<pair<int,int>,pair<int,int> > ppp;
typedef pair<pair<int,int>,int> ppi;

const long double PI=acos(-1);
const int INF=(int)1e18;
const int MOD=(int)1e9+7;
const int N = 2e5+1;

void solve_case()
{
    int n;
    cin >> n;

    __int128 a=1,b=1,c;

    for(int i=0;i<n;i++)
    {
        c = a;
        a = a + b;
        b = c;
    }

    string ans = "";
    while(a > 0)
    {
        ans = (char)((a%10) + 48) + ans;
        a/=10;
    }

    cout << ans;

    return;
}

signed main()
{
    ios::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr);
//    freopen("maximum.in","r",stdin);
//    freopen("maximum.out","w",stdout);

    int t = 1;
//    cin >> t;

    while(t--)
    {
        solve_case();
    }

    return 0;
}

/*

t*(t+1)/2 == n

t^2 + t - n == 0

D=1+4*n

x1 = (sqrt(D)+1)/2

0 1 1 2 1 2 2 3 1  2  2  3  2  3  3  4

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

0 1 2 3 4 5 6 7 8  9 10 11 12 13 14 15
*/