# include <fstream>
# define MOD 666013
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");

long long A[2][2]={{1,1},{0,0}}; // mat initiala
long long C[2][2]={{0,1},{1,1}}; // matricea pe care o ridic la puterea N
long long sol[2][2]={{1,0},{0,1}}; // matricea in care la final se va afla solutia; initializata cu elementul neutru

long long Fn;
int n;

void inmultire(long long a[][2], long long b[][2])
{
    int c[2][2]; // produsul a*b
    for(int i=0; i<2; i++)
        for(int j=0; j<2; j++)
        {
            c[i][j] = 0;
            for(int k=0; k<2; k++)
                c[i][j] =(c[i][j] + (long long) a[i][k]*b[k][j])%MOD; // simulam operatie de inmultire a matricilor
        }
    for(int i=0; i<2; i++)
        for(int j=0; j<2; j++)
            a[i][j] = c[i][j];
}

void ridicare_la_putere(int n)
{
    while(n)
    {
        if(n%2==1) { n--; inmultire(sol,C); }
        else { n/=2; inmultire(C,C); }
    }
}

int main()
{
    fin>>n;
    ridicare_la_putere(n-1); // sol=c^n
    inmultire(A,sol); // sol=A*c^n
    Fn=A[0][0];
    fout<<Fn;
    return 0;
}