#include <iostream>
#include <stdio.h>

#define m 666013

using namespace std;

long long k;

/** A^2
 ( a , b ) ( a , b )   ( a*a+b*c , a*b+b*d )
 (       )*(       ) = (                   )
 ( c , d ) ( c , d )   ( c*a+d*c , c*b+d*d )
*/
struct matrix{
    long long a,b,c,d;

    void square()
    {
        long long A = (a*a+b*c) % m;    long long B = (a*b+b*d) % m;
        long long C = (c*a+d*c) % m;    long long D = (c*b+d*d) % m;

        a=A; b=B; c=C; d=D;
    }

    void multiplyZ(long long aa, long long bb, long long cc, long long dd)
    {
        long long A = (a*aa+b*cc) % m;  long long B = (a*bb+b*dd) % m;
        long long C = (c*aa+d*cc) % m;  long long D = (c*bb+d*dd) % m;

        a=A; b=B; c=C; d=D;
    }
} M;

void lgpow(long long k)
{
    if( k<=1 )
        return;
    if( k%2 == 0 )
    {
        M.square();
        lgpow(k/2);
        return;
    }
    if( k%2 == 1 )
    {
        long long x1,x2,x3,x4;
        x1=M.a; x2=M.b; x3=M.c; x4=M.d;

        lgpow(k-1);
        M.multiplyZ(x1,x2,x3,x4);
        return;
    }
}

int main()
{
    freopen ("kfib.in","r",stdin);
    freopen ("kfib.out","w",stdout);

    scanf("%lld", &k);

    M.a = 0;  M.b = 1;
    M.c = 1;  M.d = 1;

    lgpow(k-1);

    printf("%lld", M.d);
    return 0;
}