#include <bits/stdc++.h>
#define MOD 666013
using namespace std;
int A[3][3];
int Mat[3][3];
int Res[2][2];
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]+=(1LL*A[i][k]*B[k][j])%MOD;
}
int main(){
    int n;
    scanf("%d",&n);
    if(n==1) return printf("1\n");
    A[1][2]=A[2][1]=A[2][2]=1;
    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(Mat[1][1]==0&&Mat[1][2]==0&&Mat[2][1]==0&&Mat[2][2]==0)
                Mat[1][1]=A[1][1],Mat[1][2]=A[1][2],Mat[2][1]=A[2][1],Mat[2][2]=A[2][2];
            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;
}