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

const long long mod=666013;
int n,a[2][2],solv[2][2],z[2][2];
void copyx(int a[2][2],int b[2][2])
{
    for(int i=0;i<=1;i++)
        for(int j=0;j<=1;j++)
        a[i][j]=b[i][j];
}

void const_matrix()
{
    z[0][0]=0;
    z[0][1]=1;
    z[1][0]=1;
    z[1][1]=1;
}

void matrix_multiplication(int a[][2],int b[][2])
{
    int c[2][2]={0};
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
    {
        for(int nr=0;nr<2;nr++)
            c[i][j]=(c[i][j]+((1ll*a[i][nr]*b[nr][j])%mod))%mod;

    }
    copyx(a,c);
}

void exp(int expo)
{
    copyx(solv,z);
    expo--;
    while(expo)
    {
        if(expo%2)
        {
            expo--;
            matrix_multiplication(solv,z);
        }
        expo/=2;
        matrix_multiplication(z,z);
    }
}

int main()
{
    fin>>n;
    const_matrix();
    exp(n-1);
    fout<<solv[1][1];
    return 0;
}