#include<fstream>
#define mod 666013
using namespace std;
ifstream cin ("kfib.in" );
ofstream cout("kfib.out");
int A[3][3], k, B[3][3];
void afisare(int a[3][3])
{
    for(int i=1;i<=2;i++){
        for(int j=1;j<=2;j++)
        cout<<a[i][j]<<" ";
    cout<<"\n";
    }
}
void copiaza( int mat1[3][3], int mat2[3][3] ){
    for(int i=1;i<=2;i++)
        for(int j=1;j<=2;j++)
            mat1[i][j]=mat2[i][j];

}
void inmultire(int  mat1[3][3],int  mat2[3][3], int mat3[3][3] ){

    mat3[1][1]=((1ll*mat1[1][1]*mat2[1][1])%mod+(1ll*mat1[1][2]*mat2[2][1])%mod)%mod;
    mat3[1][2]=((1ll*mat1[1][1]*mat2[1][2])%mod+(1ll*mat1[1][2]*mat2[2][2])%mod)%mod;
    mat3[2][1]=((1ll*mat1[2][1]*mat2[1][1])%mod+(1ll*mat1[2][2]*mat2[2][1])%mod)%mod;
    mat3[2][2]=((1ll*mat1[2][1]*mat2[1][2])%mod+(1ll*mat1[2][2]*mat2[2][2])%mod)%mod;
}
void ridicare(int B[3][3], int n){
    int C[3][3];
    if(n>1)
    {
        ridicare(B,n/2);
        inmultire(B,B,C);//C=B*B
        if(n%2!=0){
            inmultire(C,A,B);//B=C*A
        }
        else
            copiaza(B,C);
    }
    else
        copiaza(B,A);
}

int main(){
    cin>>k;
    A[1][1]=0;
    A[1][2]=1;
    A[2][1]=1;
    A[2][2]=1;
    if(k==1)
        cout<<1;
    else
        if(k==0)
            cout<<0;
        else
        {
            copiaza(B,A);
            ridicare(B, k-1);
            cout<<(B[2][2])%mod;
        }
    return 0;
}