#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;
}
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;
    A[1][2]=A[2][1]=A[2][2]=1;
    bool first=0;
    for(int i=0;(1<<i)<=n-1;++i){
        if((1<<i)&(n-1)){
            int aux[3][3];
            aux[1][1]=Mat[1][1];
            aux[1][2]=Mat[1][2];
            aux[2][1]=Mat[2][1];
            aux[2][2]=Mat[2][2];
            if(!first)
                Mat[1][1]=A[1][1],Mat[1][2]=A[1][2],Mat[2][1]=A[2][1],Mat[2][2]=A[2][2],first=1;
            else{
                Mat[1][1]=Mat[1][2]=Mat[2][1]=Mat[2][2]=0;
                Prod(A,aux,Mat);
            }
        }
        int aux[3][3];
        aux[1][1]=A[1][1];
        aux[1][2]=A[1][2];
        aux[2][1]=A[2][1];
        aux[2][2]=A[2][2];
        A[1][1]=A[1][2]=A[2][1]=A[2][2]=0;
        Prod(aux,aux,A);
    }
    int fib=Mat[2][2];
    printf("%d\n",fib);
    return 0;
}