#include <stdio.h>
#define mod 666013
using namespace std;

void mult(long long int a[][2], long long int b[][2]){
    long long int q,w,e,r;
    q=(a[0][0]*b[0][0]+a[0][1]*b[1][0])%mod;
    r=(a[0][0]*b[0][1]+a[0][1]*b[1][1])%mod;
    e=(a[1][0]*b[0][0]+a[1][1]*b[1][0])%mod;
    w=(a[1][0]*b[0][1]+a[1][1]*b[1][1])%mod;
    a[0][0]=q;
    a[0][1]=r;
    a[1][0]=e;
    a[1][1]=w;
}
int main(){
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    long long int j,i,a[2][2],b[2][2],p;
    scanf("%lld",&p);
    if(p==1||p==2)
        b[1][1]=1;
    else
        if(p==3)
            b[1][1]=2;
        else{
                for(i=0;i<=1;i++)
                    for(j=0;j<=1;j++){
                        b[i][j]=1;
                        a[i][j]=1;
                    }
                a[0][0]=b[0][0]=0;
                p-=2;
                for(i=0;(1<<i)<=p;i++){
                    if((1<<i)&p)
                        mult(b, a);
                    mult(a, a);
                }
            }
    printf("%lld", b[1][1]);
    return 0;
}