#include <bits/stdc++.h>
#define MOD 666013
using namespace std;
int A[3][3];
int Mat[3][3];
void Prod(int A[3][3],int B[3][3],int C[3][3]){
    for(int i=1;i<=2;++i)
        for(int j=1;j<=2;++j)
            for(int k=1;k<=2;++k)
                C[i][j]=(C[i][j]+1LL*A[i][k]*B[k][j])%MOD;
}
void Copy(int A[3][3],int B[3][3]){
    for(int i=1;i<=2;++i)
        for(int j=1;j<=2;++j)
            A[i][j]=B[i][j];
}
void Set(int A[3][3]){
    for(int i=1;i<=2;++i)
        for(int j=1;j<=2;++j)
            A[i][j]=0;
}
int main(){
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    int n;
    scanf("%d",&n);
    if(n==1) return printf("1\n"),0;
    /// Matricea de inmultit
    A[1][2]=A[2][1]=A[2][2]=1;
    /// Matricea unitate
    Mat[1][1]=Mat[2][2]=1;
    for(int i=0;(1<<i)<=n-1;++i){
        if((1<<i)&(n-1)){
            int aux[3][3];
            Copy(aux,Mat);
            Set(Mat);
            Prod(A,aux,Mat);
        }
        int aux[3][3];
        Copy(aux,A);
        Set(A);
        Prod(aux,aux,A);
    }
    printf("%d\n",Mat[2][2]);
    return 0;
}