#include <iostream>
#include <fstream>

using namespace std;

const long long r = 666013;

ifstream fin("kfib.in");
ofstream fout("kfib.out");

void produs(long long p[2][2], long long a[2][2],long long b[2][2]) //inmultirea a doua matrice de 2x2
{
    int aux[2][2];
    aux[0][0]=(a[0][0] * b[0][0]%r + a[0][1] * b[1][0]%r)%r;
    aux[0][1]=(a[0][0] * b[0][1]%r + a[0][1] * b[1][1]%r)%r;
    aux[1][0]=(a[1][0] * b[0][0]%r + a[1][1] * b[1][0]%r)%r;
    aux[1][1]=(a[1][0] * b[0][1]%r + a[1][1] * b[1][1]%r)%r;
    p[0][0]=aux[0][0];
    p[0][1]=aux[0][1];
    p[1][0]=aux[1][0];
    p[1][1]=aux[1][1];
}

void putere(long long p[2][2], long long a[2][2], long long n)
{
    if(n==0)
    {
        p[0][0]=p[1][1]=1;
        p[0][1]=p[1][0]=0;
        return;
    }
    if(n%2!=0)
    {
        long long aux[2][2];
        aux[0][0]=a[0][0];
        aux[0][1]=a[0][1];
        aux[1][0]=a[1][0];
        aux[1][1]=a[1][1];
        produs(a,a,a);
        putere(p,a,n/2);
        produs(p,p,aux);
    }
    else
    {
        produs(a,a,a);
        putere(p,a,n/2);
    }
}

int main()
{
    long long A[2][2],fib[2][2],p[2][2];
    long long k;
    fin>>k;

    fib[0][0]=A[0][0]=1;
    fib[0][1]=A[0][1]=1;
    A[1][0]=1;
    fib[1][1]=A[1][1]=0;
    fib[1][0]=0;

    putere(p,A,k-1);//ridicam pe A la puterea k-1

    produs(p,p,fib);
    fout<<p[0][0];
    return 0;
}