#include <bits/stdc++.h>
#define NMax 1400005
#define modulo  666013

using namespace std;

ifstream fin ("kfib.in");
ofstream fout ("kfib.out");
int a[NMax], n, K;

int main()
{
    bool gata = 0;
    fin >> n;

    a[0] = 0;
    a[1] = a[2] = 1;
    K = 2;

    while(!gata)
    {
        K++;
        a[K] = a[K - 1] + a[K - 2];
        if(a[K] >= modulo)
            a[K] -= modulo;
        if(a[K] == 1 && a[K - 1] == 0)
            gata = 1;
    }

    K--;
    fout << a[n % K]<<"\n";

    return 0;
}