#include <iostream>
#include <fstream>
#define m 666013
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
long long z1=0,z2=1,z3=1,z4=1,a1=0,a2=1,a3=1,a4=1,aux1,aux2,aux3,aux4;

void ridicare(long long n)
{
    if(n!=1)
    {
        if(n%2==0)
        {
            ridicare(n/2);
            aux1=(z1*z1)%m+(z2*z3)%m;
            aux2=(z1*z2)%m+(z2*z4)%m;
            aux3=(z3*z1)%m+(z4*z3)%m;
            aux4=(z3*z2)%m+(z4*z4)%m;
            z1=aux1%m;
            z2=aux2%m;
            z3=aux3%m;
            z4=aux4%m;
        }
        else
        {
            ridicare((n-1)/2);
          aux1=(z1*z1)%m+(z2*z3)%m;
            aux2=(z1*z2)%m+(z2*z4)%m;
            aux3=(z3*z1)%m+(z4*z3)%m;
            aux4=(z3*z2)%m+(z4*z4)%m;
            z1=aux1%m;
            z2=aux2%m;
            z3=aux3%m;
            z4=aux4%m;
            aux1=(z1*a1)%m+(z2*a3)%m;
            aux2=(z1*a2)%m+(z2*a4)%m;
            aux3=(z3*a1)%m+(z4*a3)%m;
            aux4=(z3*a2)%m+(z4*a4)%m;
            z1=aux1%m;
            z2=aux2%m;
            z3=aux3%m;
            z4=aux4%m;
        }
    }

}
int main()
{
    long long n;
    fin>>n;
    if(n==0) fout<<0;
    else if(n==1||n==2) fout<<1;
    else
    {
        ridicare(n-2);
        fout<<(z2+z4)%m;
    }
}