#include<iostream>
#include<fstream>

using namespace std;

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

bool v[31];

long long  k, a = 1, b = 1, s = 0, A[3][3], C[3][3];

void binar()
{
    int k1 = k, nr = 1024 * 1024 * 1024;
    for(int i = 30; i >=0; --i)
    {
        if(nr <= k1)
        {
            k1 -= nr;
            v[i] = 1;
        }
        nr /= 2;
    }
}

void matrice()
{
    A[1][2] = 1;
    A[2][1] = 1;
    A[2][2] = 1;
    C[1][1] = 1;
    C[2][2] = 1;
}

void inmMatrice()
{
    long long  B[3][3];
    B[1][1] = A[1][1] * A[1][1] + A[1][2] * A[2][1];
    B[1][1] %= 666013;
    B[1][2] = A[1][1] * A[1][2] + A[1][2] * A[2][2];
    B[1][2] %= 666013;
    B[2][1] = A[2][1] * A[1][1] + A[2][2] * A[2][1];
    B[2][1] %= 666013;
    B[2][2] = A[2][1] * A[1][2] + A[2][2] * A[2][2];
    B[2][2] %= 666013;
    A[1][1] = B[1][1];
    A[1][2] = B[1][2];
    A[2][1] = B[2][1];
    A[2][2] = B[2][2];
}

void inmMatrice1()
{
    long long B[3][3];
    B[1][1] = A[1][1] * C[1][1] + A[1][2] * C[2][1];
    B[1][1] %= 666013;
    B[1][2] = A[1][1] * C[1][2] + A[1][2] * C[2][2];
    B[1][2] %= 666013;
    B[2][1] = A[2][1] * C[1][1] + A[2][2] * C[2][1];
    B[2][1] %= 666013;
    B[2][2] = A[2][1] * C[1][2] + A[2][2] * C[2][2];
    B[2][2] %= 666013;
    C[1][1] = B[1][1];
    C[1][2] = B[1][2];
    C[2][1] = B[2][1];
    C[2][2] = B[2][2];
}

void funct()
{
    for(int i = 0; i <= 30; ++i)
    {
        if(v[i] == 1)
        {
            inmMatrice1();
        }
        inmMatrice();
    }
}

int main()
{
    fin>>k;
    //k-=1;
    binar();
    matrice();
    funct();
    /*for(int i = 1; i <= 2; ++i)
    {
        for(int j = 1; j <= 2; ++j)
        {
            cout<<C[i][j]<<" ";
        }
        cout<<endl;
    }*/
    if(k == -1) fout<<'0';
    else if(k == 0) f1out<<'1';
    else fout<<C[1][2] % 66013;
}