#include <algorithm>
#include <bits/stdc++.h>
#include <queue>
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
long long n;
long long sol[3][3],c[3][3],fin[3][3],mod=666013;

void inm(long long a[3][3],long long b[3][3]){
    long long v[3][3];
    for(int i=1;i<=2;i++){
        for(int j=1;j<=2;j++){
            v[i][j]=0;
            for(int k=1;k<=2;k++){
                v[i][j]=(v[i][j]+((a[i][k]*b[k][j])%mod))%mod;
            }
        }
    }
    for(int i=1;i<=2;i++){
        for(int j=1;j<=2;j++)
        a[i][j]=v[i][j];
    }
}

void exp(long long pow){
    while(pow){
        if(pow%2==1){
            pow--;
            inm(sol,c);
        }
        pow/=2;
        inm(c,c);
    }
}

int main() {
    sol[1][1]=sol[2][2]=c[1][2]=c[2][1]=c[2][2]=fin[1][1]=fin[1][2]=1;
    f>>n;
    exp(n+1);
    inm(sol,fin);
    g<<sol[1][1];
}