#include <iostream>
#include <fstream>
using namespace std;

#define MOD 666013

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

void inm_matr(long long A[2][2], long long B[2][2])
{
    long long AB[2][2]={0,0};
    int i, j, k;
    for(i = 0; i < 2; i++)
        for(j = 0; j < 2; j++)
        {

            for(k = 0; k < 2; k++)
                AB[i][j] += ( (A[i][k] * B[k][j]) % MOD );
            AB[i][j] %= MOD;
        }
    for(i = 0; i < 2; i++)
        for(j = 0; j < 2; j++)
            B[i][j] = AB[i][j];

}

int FibClasic(int k)
{
    int a = 0, b = 1, c;
    if( k == 0 )
        return 0;
    if ( k <= 2 )
        return 1;
    k--;
    while(k > 0)
    {
        c = (a + b) % MOD;
        a = b;
        b = c;
        k--;
    }
    return c;
}

long long matr[2][2], formula[2][2];

int main()
{
    int K;
    fin>>K;

    //cout<<FibClasic(K);

    matr[0][0] = 0;       matr[0][1] = 1;
    matr[1][0] = 1;       matr[1][1] = 1;

    formula[0][0] = 0;    formula[0][1] = 0;
    formula[1][0] = 1;    formula[1][1] = 0;

    if(K == 0)
    {
        fout<<0;
        return 0;
    }
    if(K <= 2)
    {
        fout<<1;
        return 0;
    }

    while ( K > 1  )
    {
        if(K % 2 == 0)
        {
            inm_matr(matr, matr);
            K /= 2;
        }
        else
        {
            inm_matr(matr, formula);
            K--;
        }
    }
    inm_matr(matr, formula);
    fout<<formula[0][0];

    fin.close();
    fout.close();
    return 0;
}