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

using namespace std;

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

long long n, A[NMax][NMax], B[NMax][NMax];
void prod_mat(long long A[NMax][NMax], long long B[NMax][NMax], long long dim)
{
    long long 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 put_mat(long long A[NMax][NMax], int n)
{
    while(n)
    {
        if(n%2==1) prod_mat(A,B,2);
        prod_mat(B,B,2);
        n/=2;
    }

}

int main()
{
    fin>>n;
    
    A[0][1]=A[1][0]=A[1][1]=1;
    B[0][1]=B[1][0]=B[1][1]=1;

    put_mat(A,n);

    fout<<A[0][0];
    
    return 0;
}