#include <iostream>
#include<fstream>
using namespace std;
long long n,i,j,k,l,S[3][3],M[3][3],A[3][3];
void inmult(long long A[][3],long long B[][3],long long C[][3]){
    for(i=0;i<2;i++)
        for(j=0;j<2;j++)
            for(k=0;k<2;k++)
            C[i][j]=(C[i][j]+A[i][k]*B[k][j])%666013;
}
void putere(int p,long long M[][3],long long A[][3]){
    if(p==0){
    M[0][0]=M[1][1]=1;
    M[1][0]=M[0][1]=0;
    return;
    }
    putere(p/2,M,A);
    if(p%2==1){
        S[0][0]=S[1][0]=S[0][1]=S[1][1]=0;
        inmult(M,M,S);
        M[0][0]=M[1][1]=M[1][0]=M[0][1]=0;
        inmult(S,A,M);
    }
    else{
    S[0][0]=S[1][0]=S[0][1]=S[1][1]=0;
        inmult(M,M,S);
        for(i=0;i<2;i++)
            for(j=0;j<2;j++)
            M[i][j]=S[i][j];
    }
}
int main()
{
    ifstream cin("kfib.in");
    ofstream cout("kfib.out");
    cin>>n;
    A[1][1]=1;
    A[1][0]=1;
    A[0][1]=1;
    putere(n-1,M,A);
    cout<<M[1][1];
}