#include <bits/stdc++.h>

using namespace std;

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

const int mod=666013;
int n;
struct matrix
{
    int lin, col;
    int a[3][3];
};
matrix A, B, K;

matrix multiplication(matrix X, matrix Y)
{
    matrix Z;
    Z.lin=X.lin;
    Z.col=Y.col;
    for(int i=1; i<=Z.lin; i++)
        for(int j=1; j<=Z.col; j++)
        {
            Z.a[i][j]=0;
            for(int k=1; k<=X.col; k++)
                Z.a[i][j]=(Z.a[i][j]+1LL*X.a[i][k]*Y.a[k][j]%mod)%mod;
        }
    return Z;
}

matrix power(matrix X, int p)
{
    matrix Z=X;
    p--;
    while(p)
    {
        if(p%2==1)
            Z=multiplication(Z, X);
        X=multiplication(X, X);
        p/=2;
    }
    return Z;
}

int main()
{
    fin >> n;
    if(n==0)
        fout << 0;
    else if(n==1)
        fout << 1;
    else
    {
        K.lin=K.col=2;
        K.a[1][1]=0;
        K.a[1][2]=1;
        K.a[2][1]=1;
        K.a[2][2]=1;
        A.lin=1;
        A.col=2;
        A.a[1][1]=0;
        A.a[1][2]=1;
        B=multiplication(A, power(K, n-1));
        fout << B.a[1][2];
    }
    return 0;
}