#include <cstdio>
#include <iostream>
using namespace std;

int n,v[100],vv[100];
int main()
{
    FILE *f=fopen("kfib.in","r");
    fscanf(f,"%d",&n);

    FILE *g=fopen("kfib.out","w");
    cin>>n;
 n=n-2;
    long long a[3][3];
    long long vr[3][3];
    a[1][1]=1;
    a[1][2]=1;
    a[2][1]=1;
    a[2][2]=0;



    int k=1;
    while(n)
    {
        v[k++]=n%2;
        n=n/2;
    }
    int o=0;
    for(int i=1; i<k; i++)
    {
        if(v[i]==1)
            vv[++o]=(v[i]<<i-1);
    }

    int nrnou=0;




    long long anou[3][3];
    anou[1][1]=1;
    anou[1][2]=1;
    anou[2][1]=1;
    anou[2][2]=1;

    int p=1;
    k=0;
    int    ok=99;
    while (ok>2)
    {

        if(p==vv[k+1])
        {

            for(int ima=1; ima<=2; ima++)
                for(int jma=1; jma<=2; jma++)
                {
                    vr[ima][jma]=0;

                    for(int kma=1; kma<=2; kma++)
                        vr[ima][jma]+=(anou[ima][kma]*a[kma][jma])%666013;

                }

            anou[1][1]=vr[1][1];
            anou[1][2]=vr[1][2];
            anou[2][1]=vr[2][1];
            anou[2][2]=vr[2][2];

         k++;

        }


        if(vv[k+1]==0) ok=1;

        for(int ima=1; ima<=2; ima++)
            for(int jma=1; jma<=2; jma++)
            {
                vr[ima][jma]=0;

                for(int kma=1; kma<=2; kma++)
                    vr[ima][jma]+=(a[ima][kma]*a[kma][jma])%666013;


            }
        a[1][1]=vr[1][1];
        a[1][2]=vr[1][2];
        a[2][1]=vr[2][1];
        a[2][2]=vr[2][2];
        p=p*2;



    }


    fprintf(g,"%d",anou[1][1]%666013);
    return 0;
}