#include <fstream>
#define MOD 666013
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
long long A[2][2],R[2][2],exp,k;
void inm(long long A[][2],long long B[][2]){
    int C[2][2],i,j,k;
    for(i=0;i<=1;i++)
        for(j=0;j<=1;j++)
            C[i][j]=0;
    for(i=0;i<=1;i++)
        for(j=0;j<=1;j++)
            for(k=0;k<=1;k++)
            C[i][j]+=(A[i][k]*B[k][j])%MOD;
    for(i=0;i<=1;i++)
        for(j=0;j<=1;j++)
            B[i][j]=C[i][j]%MOD;
    }
int main()
{
    f>>k;
    R[0][0]=R[1][1]=1;
    while(k!=0){
        exp=1;
        A[0][0]=0;
        A[1][0]=A[1][1]=A[0][1]=1;
        while(exp*2<=k){
            exp=exp*2;
            inm(A,A);
        }
        inm(A,R);
        k-=exp;
    }
    g<<R[1][0];
    return 0;
}