#include <iostream>
#include <fstream>
using namespace std;
int a[3][3],b[3][3],c[3][3];


int fibo(int n)
{
     a[1][1]=b[1][1]=1;
     a[2][1]=b[2][1]=1;
     a[1][2]=b[1][2]=1;
     a[2][2]=b[2][2]=0;

    while(n)
    {
        if(n%2)
        {
            c[1][1]=((long long)a[1][1]*b[1][1]+(long long)a[1][2]*b[2][1])%666013;
            c[2][1]=((long long)a[2][1]*b[1][1]+(long long)a[2][2]*b[2][1])%666013;
            c[1][2]=((long long)a[1][1]*b[1][2]+(long long)a[1][2]*b[2][2])%666013;
            c[2][2]=((long long)a[2][1]*b[1][2]+(long long)a[2][2]*b[2][2])%666013;

            a[1][1]=c[1][1];
            a[2][1]=c[2][1];
            a[1][2]=c[1][2];
            a[2][2]=c[2][2];
            n--;
        }
        else
        {
            c[1][1]=(b[1][1]*(long long)b[1][1]+b[1][2]*(long long)b[2][1])%666013;
            c[2][1]=(b[2][1]*(long long)b[1][1]+b[2][2]*(long long)b[2][1])%666013;
            c[1][2]=(b[1][1]*(long long)b[1][2]+b[1][2]*(long long)b[2][2])%666013;
            c[2][2]=(b[2][1]*(long long)b[1][2]+b[2][2]*(long long)b[2][2])%666013;

            b[1][1]=c[1][1];
            b[2][1]=c[2][1];
            b[1][2]=c[1][2];
            b[2][2]=c[2][2];

            n/=2;
        }

    }
    return a[2][2];
}
int main()
{
    int i,j;
    ifstream fin ("kfib.in");
    ofstream fout ("kfib.out");
    long long n;
    fin>>n;
    fout<<(fibo(n));
    return 0;
}