#include <stdio.h>
#define MOD 666013
long long a[3][3],d[3][3];


    void exp_matrice(long long y[3][3],long long z[3][3],long long q[3][3],int mod){
    long long x[3][3];
    int i,j;




    if(mod == 2){
    x[1][1] = (y[1][1] * z[1][1])%MOD + (y[1][2] * z[2][1])%MOD;
    x[1][2] = (y[1][1] * z[2][1])%MOD + (y[1][2] * z[2][2])%MOD;

    x[2][1] = (y[2][1] * z[1][1])%MOD + (y[2][2] * z[2][1])%MOD;
    x[2][2] = (y[2][1] * z[1][2])%MOD + (y[2][2] * z[2][2])%MOD;

    q[1][1] = x[1][1]%MOD;
    q[1][2] = x[1][2]%MOD;
    q[2][1] = x[2][1]%MOD;
    q[2][2] = x[2][2]%MOD;
    }
    else{

    x[1][1] = (y[1][1] * z[1][1])%MOD + (y[1][2] * z[2][1])%MOD;
    x[2][1] = (y[2][1] * z[1][1])%MOD + (y[2][2] * z[2][1])%MOD;


    q[1][1] = x[1][1]%MOD;
    q[2][1] = x[2][1]%MOD;
    }



}

    void putere(int k){
    FILE *g;
    g=fopen("kfib.out","w+");

        long long c[3][3],rez[3][3];
        a[1][1] = 0;
        a[1][2] = 1;
        a[2][1] = 1;
        a[2][2] = 1;
        c[1][1] = 0;
        c[1][2] = 1;
        c[2][1] = 1;
        c[2][2] = 1;


        rez[1][1] = 0;
        rez[2][1] = 1;

        while(k)
        {
            if(k % 2 ==0)
            {
                k = k / 2;
                exp_matrice(c,c,c,2);
            }
            else
            {
                --k;
                exp_matrice(c,rez,rez,1);
            }
        }

        fprintf(g,"%d",rez[2][1]);



    }

int main()


{

    FILE *f,*g;
    int k;

    f=fopen("kfib.in","r");
    g=fopen("kfib.out","w+");

    fscanf(f,"%d",&k);

    putere(k-1);


}