#include<bits/stdc++.h>
#define NMax 2
#define MOD 666013

using namespace std;

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

int n,fib[NMax][NMax],mat[NMax][NMax]={{0,1},{1,1}},rez[NMax][NMax];
void prod_mat(int A[NMax][NMax], int B[NMax][NMax], int dim)
{
    int C[NMax][NMax];
    for(int i=0; i<dim; i++)
        for(int j=0; j<dim; j++)
        {
            C[i][j]=0;
            for(int k=0; k<dim; k++)
                C[i][j]=(C[i][j]+A[i][k]*B[k][j]%MOD)%MOD;
        }
    
    for(int i=0; i<dim; i++)
        for(int j=0; j<dim; j++)
            A[i][j]=C[i][j];
}

void putere(int A[NMax][NMax], int b, int rez[NMax][NMax])
{
    if(b==0)
    {   
        rez[0][0]=rez[1][1]=1;
        rez[0][1]=rez[1][0]=0;
    }
    else
    {
        putere(A,b/2,rez);
        
        prod_mat(rez,rez,2);

        if(b%2==1) prod_mat(rez,A,2);
    }
}

int main()
{
    fin>>n;
        putere(mat,n,rez);

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

        prod_mat(fib,rez,2);

        fout<<rez[0][1];
    return 0;
}