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

using namespace std;

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

long long k;

void multiplyMatrix( long long a[n][n], long long b[n][n] )
{
    long long auxiliary_Value[n][n];
    auxiliary_Value[0][0] = auxiliary_Value[0][1] = auxiliary_Value[1][0] = auxiliary_Value[1][1] = 0;

    for ( int i = 0; i < n; ++i )
        for ( int j = 0; j < n; ++j )
            for ( int k = 0; k < n; ++k )
                auxiliary_Value[i][j] += (a[i][k]*b[k][j])%MOD;

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

long long answer ()
{
    long long current_Value[n][n];
    current_Value[0][0] = current_Value[1][1] = 1;
    current_Value[1][0] = current_Value[0][1] = 0;

    long long constant_Value[n][n];
    constant_Value[0][0] = 0;
    constant_Value[0][1] = constant_Value[1][0] = constant_Value[1][1] = 1;

    while ( k )
    {
        if ( k%2 )
        {
            multiplyMatrix(current_Value, constant_Value);
            k--;
        }
        else
        {
            multiplyMatrix(constant_Value, constant_Value);
            k /= 2;
        }
    }

    return current_Value[1][0];
}

int main()
{
    fin>>k;
    fout<<answer();
}