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

#define MOD 666013
using namespace std;
ofstream out("kfib.out");

int n;
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 )
{
    for(;p;p>>=1)
    {
        if(p&1)
        {
            mult(M,Z);
        }
        mult(Z,Z);
    }
}

int main()
{

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

    M[0][0] = 1;
    M[0][1] = 1;

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

    bin_pow(n-1);
    out << M[0][1] % MOD;

    return 0;

}