#include <stdio.h>

#define MOD 666013

void Mult(long long F[2][2], long long M[2][2]);
void exp(long long F[2][2], long long n);
long long fib(long long n);
void exp(long long F[2][2], long long n);
void Mult(long long F[2][2], long long M[2][2]);

int main()
{
    freopen("kfib.in", "r", stdin);
    freopen("kfib.out", "w", stdout);
    long long n;
    scanf("%lld",&n);
    printf("%lld\n",fib(n));
    return 0;
}
long long fib(long long n)
{
    long long F[2][2] = {{1,1},{1,0}};
    if (n == 0)
        return 0;
    exp(F, n-1);
    return F[0][0] % MOD;
}
void exp(long long F[2][2], long long n)
{
    if( n == 0 || n == 1)
        return;
    long long M[2][2] = {{1,1},{1,0}};
    
    exp(F, n/2);
    Mult(F, F);
    
    if (n%2 != 0)
        Mult(F, M);
}

void Mult(long long F[2][2], long long M[2][2])
{
    long long x =  (F[0][0]*M[0][0] + F[0][1]*M[1][0]) % MOD;
    long long y =  (F[0][0]*M[0][1] + F[0][1]*M[1][1]) % MOD;
    long long z =  (F[1][0]*M[0][0] + F[1][1]*M[1][0]) % MOD;
    long long w =  (F[1][0]*M[0][1] + F[1][1]*M[1][1]) % MOD;
    
    F[0][0] = x;
    F[0][1] = y;
    F[1][0] = z;
    F[1][1] = w;
}