#include <stdio.h>

#define MOD 666013LL

typedef struct 
{
    long long a[2][2];
} Matrix;

Matrix multiply(Matrix A, Matrix B) 
{
    Matrix C;
    int i, j, k;
    for (i=0; i<2;i++)
        for (j=0;j<2;j++) {
            C.a[i][j]= 0;
            for (k=0;k<2;k++)
                C.a[i][j]=(C.a[i][j] + A.a[i][k] * B.a[k][j])%MOD;
        }
    return C;
}

Matrix matpow(Matrix M, long long exp) 
{
    Matrix result;
    result.a[0][0]=1; result.a[0][1]=0;
    result.a[1][0]=0; result.a[1][1]=1;

    while(exp > 0) 
    {
        if (exp % 2 == 1) result = multiply(result, M);
        M=multiply(M, M);
        exp /= 2;
    }
    return result;
}

int main() 
{
    FILE *fin=fopen("kfib.in","r");
    FILE *fout=fopen("kfib.out","w");
    long long k;
    fscanf(fin,"%lld",&k);
    if (k==0) 
    {
        fprintf(fout, "0\n");
    } else if (k==1) 
    {
        fprintf(fout,"1\n");
    } else 
    {
        Matrix Z;
        Z.a[0][0]=0; Z.a[0][1]=1;
        Z.a[1][0]=1; Z.a[1][1]=1;
        Matrix R = matpow(Z,k);
        fprintf(fout, "%lld\n", R.a[0][1]);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}