#include <iostream>
#include <fstream>
#include <vector>

using namespace std;
ofstream out("kfib.out");

int n;
const int MOD = 666013;
int M[2][2] , Z[2][2];

void mult(int a[2][2] , int b[2][2])
{

    int c[2][2];

    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] += 1LL *  a[i][k] * b[k][j] %MOD;
                    if(c[i][j] >= MOD)
                        c[i][j] -=MOD;
                }
        }
    }

    for( int i = 0 ; i < 2 ; i++)
    {
        for( int j = 0 ; j < 2 ; j++)
        {
            a[i][j] = c[i][j];
        }
    }
}

void bin_pow( int p ,int M[2][2] )
{
    M[0][0] = 0;
    M[1][1] = 1;

    for(; p ; p>>=1 )
    {
        if(p&1)
        {
            mult(M,Z);
        }
        mult(Z,Z);
    }
}

int main()
{

    ifstream in("kfib.in");
    in >> n;


    Z[0][0] = 0;
    Z[0][1] = 1;
    Z[1][0] = 1;
    Z[1][1] = 1;

    bin_pow(n-1,M);
    out << M[1][1];

    return 0;

}