#include <fstream>

using namespace std;

long long x,y,n,i,j,z;

int main()
{
    ifstream f("kfib.in");
    ofstream g("kfib.out");
    f>>n;
    x=1;y=1;
    n=n%(2+666013*2);

    for (i=3;i<=n;i++)
    {
        z=(x+y)%666013;
        x=y;
        y=z;
    }

    g<<y;
    f.close();
    g.close();
    return 0;
}