#include <fstream>
using namespace std;

void inmult_matr_2x2(long long A[2][2],long long B[2][2],long long C[2][2])
{
    C[0][0]=A[0][0]%666013*B[0][0]%666013+A[0][1]%666013*B[1][0]%666013;
    C[0][1]=A[0][0]%666013*B[0][1]%666013+A[0][1]%666013*B[1][1]%666013;
    C[1][0]=A[1][0]%666013*B[0][0]%666013+A[1][1]%666013*B[1][0]%666013;
    C[1][1]=A[1][0]%666013*B[0][1]%666013+A[1][1]%666013*B[1][1]%666013;
}

void set_matr(long long A[2][2],long long B[2][2])
{
    A[0][0]=B[0][0];
    A[0][1]=B[0][1];
    A[1][0]=B[1][0];
    A[1][1]=B[1][1];
}

int main()
{
    ifstream f("kfib.in");
    ofstream g("kfib.out");
    long long k;
    long long Z[2][2]={{0,1},{1,1}},M[2]={0,1},R[2][2]={{1,0},{0,1}};
    long long temp[2][2];
    f>>k;
    k--;
    while(k!=0)
    {
        int u=k%2;
        if(u==1)
        {
            inmult_matr_2x2(R,Z,temp);
            set_matr(R,temp);
        }
        inmult_matr_2x2(Z,Z,temp);
        set_matr(Z,temp);
        k/=2;
    }
    g<<R[1][1];
    return 0;
}