#include <vector>
#include <iostream>

using namespace std;

#define UNIT        100000000
#define UNIT_LEN    8
const char *zero = "00000000";

typedef vector<int> BN;

string BN_str(BN *b)
{
    string sn = to_string(b->at(b->size() - 1));
    for (int i = b->size() - 2; i >= 0; i--) {
        string su = to_string(b->at(i));
        if (su.length() < UNIT_LEN) {
            sn += (zero + su.length());
        }
        sn += su;
    }
    return sn;
}

int BN_len(BN *b)
{
    if (!b->size()) return 0;
    int l = 0;
    for (int h = b->back(); h; h /= 10) l += 1;
    return (b->size() - 1) * UNIT_LEN + l;
}

BN BN_init(int x)
{
    BN v;
    v.push_back(x);
    return v;
}

void BN_merge(BN *a, BN *b)
{
    int carry_up = 0;
    int ib = 0;
    for (int ia = 0; ia < a->size(); ia++, ib++) {
        carry_up += a->at(ia) + b->at(ib);
        (*a)[ia] = carry_up % UNIT;
        carry_up /= UNIT;
    }
    for (; ib < b->size(); ib++) {
        carry_up += b->at(ib);
        a->push_back(carry_up % UNIT);
        carry_up /= UNIT;
    }
    for (; carry_up; carry_up /= UNIT) {
        a->push_back(carry_up % UNIT);
    }
}

int BN_digit(BN *a, int n)
{
    string sn = BN_str(a);
    if (n > sn.length()) return -1;
    return sn[n - 1] - '0';
}

int digit_of_fib_digit(int n)
{
    BN a = BN_init(1);
    BN b = BN_init(1);
    BN *p = &a;
    BN *q = &b;
    for (;;) {
        cout << BN_str(p) << endl;
        int l = BN_len(p);
        if (l >= n) {
            return BN_digit(p, n);
        }
        n -= l;
        BN_merge(p, q);
        BN *t = p;
        p = q;
        q = t;
    }
}

int main()
{
    cout << digit_of_fib_digit(800) << endl;
    return 0;
}