#include<fstream>
#include<string.h>
using namespace std;
void mult(int A[3][3],int B[3][3], int C[3][3])
{
    for(int i=1; i<3; i++)
        for(int j=1; j<3; j++)
            for(int k=1; k<3; k++)
                C[i][j]=(C[i][j] + (long long) A[i][k] * B[k][j]) % 666013;
}
int main()
{
    int A[3][3], AUX[3][3],M[3][3],K;
    ifstream q("kfib.in");
    ofstream w("kfib.out");
    q>>K;
    M[1][1]=A[1][1]=0;
    M[1][2]=A[1][2]=A[2][1]=A[2][2]=1;
    K--;
    while(K)
    {
        if(K&1)
        {
            memset(AUX,0,sizeof(AUX));
            mult(M,A,AUX);
            memcpy(M,AUX,sizeof(AUX));
        }
        memset(AUX,0,sizeof(AUX));
        mult(A,A,AUX);
        memcpy(A,AUX,sizeof(AUX));
        K/=2;
    }
    w<<M[1][2];
}