#include <fstream>

using namespace std;

ifstream f("kfib.in");
ofstream g("kfib.out");
long long k,A[3][3],B[3][3],C[3][3],C2[3][3];
void inmultire (long long C[][3],long long B[][3],long long A[][3])
{
    C[1][1]=(B[1][1]*A[1][1]%666013+B[1][2]*A[2][1]%666013)%666013;
    C[1][2]=(B[1][1]*A[1][2]%666013+B[1][2]*A[2][2]%666013)%666013;
    C[2][1]=(B[1][2]*A[1][1]%666013+B[2][2]*A[2][1]%666013)%666013;
    C[2][2]=(B[1][2]*A[1][2]%666013+B[2][2]*A[2][2]%666013)%666013;
}
void atrib (long long B[][3],long long A[][3])
{
    for(int i=1;i<=2;i++)
        for(int j=1;j<=2;j++)
            B[i][j]=A[i][j]%666013;
}
int main()
{
    f>>k;
    k--;
    C[1][1]=C[2][2]=B[1][1]=B[2][2]=1;
    A[1][2]=A[2][2]=A[2][1]=1;
    while(k!=0)
    {
        if(k%2==1)
        {
            atrib(C2,C);
            inmultire(C,C2,A);
        }
        inmultire(B,A,A);
        atrib(A,B);
        k=k/2;
    }
    g<<(C[1][1]%666013+C[2][1]%666013)%666013;
    return 0;
}