#include <iostream>
#include <fstream>

#define mod 666013
using namespace std;

ifstream f("kfib.in");
ofstream g("kfib.out");

long long n;
long long A[3][3],SOL[2][2];
long long O3[3][3];

void inmultire ( long long A[3][3] , long long B[3][3] )
{
    long long C[3][3];
    C[1][1] = (A[1][1]*B[1][1] + A[1][2]*B[2][1])%mod;
    C[1][2] = (A[1][1]*B[1][2] + A[1][2]*B[2][2])%mod;
    C[2][1] = (A[2][1]*B[1][1] + A[2][2]*B[2][1])%mod;
    C[2][2] = (A[2][1]*B[1][2] + A[2][2]*B[2][2])%mod;

    A[1][1] = C[1][1];
    A[1][2] = C[1][2];
    A[2][1] = C[2][1];
    A[2][2] = C[2][2];
}

void multiply ( long long A[2][2] , long long B[3][3] )
{
    A[1][1] = ( A[1][1]*B[1][1] + A[1][2] * B[2][1] )%mod;
    A[1][2] = ( A[1][1]*B[1][2] + A[1][2] * B[2][2] )%mod;
}

void exp_log ( long long A[3][3] , int P )
{
    while(P)
    {
        if ( P % 2 == 0 )
        {
            inmultire(A,A);
            P = P/2;
        }
        else
        {
            P--;
            inmultire(O3,A);
        }
    }
}

int main()
{
    f >> n;

    A[1][1] = 0;
    A[1][2] = A[2][1] = A[2][2] = 1;

    SOL[1][1] = SOL[1][2] = 1;

    O3[1][1] = O3[2][2] = O3[3][3] = 1;

    exp_log(A,n-1);

    multiply(SOL,O3);

    g << SOL[1][1];
    return 0;
}