#include <fstream>

#define MOD 666013;

using namespace std;

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

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

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

void inmultire(int A[3][3],int B[3][3])
{
    int SOL[3][3];
    for(int i=1;i<=2;i++)
        for(int j=1;j<=2;j++)
            SOL[i][j] = get_sum(A,B,i,j);
    for(int i=1;i<=2;i++)
        for(int 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;
    bin[0] = 0;
    while(k)
    {
        bin[++bin[0]] = k%2;
        k/=2;
    }



    for(int 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;
}