#include <stdio.h>

void matrix_multiplication( long long a[2][2] , long long b[2][2] )
{
    long long c[2][2];
    c[0][0] = a[0][0]*b[0][0] + a[0][1]*b[1][0];
    c[0][1] = a[0][0]*b[0][1] + a[0][1]*b[1][1];
    c[1][0] = a[1][0]*b[0][0] + a[1][1]*b[1][0];
    c[1][1] = a[1][0]*b[0][1] + a[1][1]*b[1][1];
    a[0][0] = c[0][0] % 666013;
    a[0][1] = c[0][1] % 666013;
    a[1][0] = c[1][0] % 666013;
    a[1][1] = c[1][1] % 666013;
}

void matrix_power( long long a[2][2], int n )
{
    long long y[2][2] = { {1,0} , {0,1} };
    if ( n == 0 )
    {
        a[0][0] = y[0][0];
        a[1][0] = y[1][0];
        a[0][1] = y[0][1];
        a[1][1] = y[1][1];
    }
    while ( n > 1 )
    {
        if ( n % 2 != 0 )
        {
            matrix_multiplication(y,a);
            n--;
        }
        matrix_multiplication(a,a);
        n = n / 2;
    }
    matrix_multiplication(a,y);
}

int main (void)
{
    long long a[2][2] = { {0,1} , {1,1} };
    int k;
    FILE *f,*out;
    f = fopen("kfib.in","r");
    out = fopen("kfib.out","w");

    fscanf(f,"%d",&k);
    if ( k == 0 )
    {
        fprintf(out,"%d",0);
        return 0;
    }
    matrix_power(a,k-1);
    fprintf(out,"%lld",a[1][1]);

    fclose(f);
    fclose(out);
    return 0;
}