#include <fstream>

#define MOD 666013;
typedef unsigned long long ULL;
using namespace std;

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

ULL M[3][3], Z[3][3], k, bin[100];

ULL get_sum(ULL A[3][3],ULL B[3][3], ULL l, ULL c)
{
    unsigned long long sum = 0;
    for(ULL i=1;i<=2;i++)
    {
        sum += A[l][i] * B[i][c];
        sum%=MOD;
    }
    return sum%MOD;
}

void inmultire(ULL A[3][3],ULL B[3][3])
{
    ULL SOL[3][3];
    for(ULL i=1;i<=2;i++)
        for(ULL j=1;j<=2;j++)
            SOL[i][j] = get_sum(A,B,i,j);
    for(ULL i=1;i<=2;i++)
        for(ULL j=1;j<=2;j++)
            A[i][j] = SOL[i][j];
}


int main()
{
    fin>>k;

    Z[1][2] = Z[2][1] = Z[2][2] = 1;
    M[1][1] = M[2][2] = 1;

    while(k)
    {
        bin[++bin[0]] = k%2;
        k/=2;
    }

    for(ULL i = bin[0]; i>0; i--)
    {
        inmultire(M,M);
        if( bin[i] )
        {
            inmultire(M,Z);
        }
    }

    fout<<M[2][1]<<'\n';
    fin.close();
    fout.close();
    return 0;
}