#include<cstdio>
#define mod 666013
using namespace std;
long long baza[2][2],a[2],b[2];
void expo(long long exp){
    long long rez[2][2],aux[2][2];
    rez[1][1]=rez[2][2]=1;
    rez[1][2]=rez[2][1]=0;
    while(exp!=0){
        if(exp%2==1){
            exp--;
            aux[1][1]=((rez[1][1]*baza[1][1])%mod+(rez[1][2]*baza[2][1])%mod)%mod;
            aux[1][2]=((rez[1][1]*baza[1][2])%mod+(rez[1][2]*baza[2][2])%mod)%mod;
            aux[2][1]=((rez[2][1]*baza[1][1])%mod+(rez[2][2]*baza[2][1])%mod)%mod;
            aux[2][2]=((rez[2][1]*baza[1][2])%mod+(rez[2][2]*baza[2][2])%mod)%mod;
            rez[1][1]=aux[1][1];
            rez[1][2]=aux[1][2];
            rez[2][1]=aux[2][1];
            rez[2][2]=aux[2][2];
        }
        else{
            exp/=2;
            aux[1][1]=((baza[1][1]*baza[1][1])%mod+(baza[1][2]*baza[2][1])%mod)%mod;
            aux[1][2]=((baza[1][1]*baza[1][2])%mod+(baza[1][2]*baza[2][2])%mod)%mod;
            aux[2][1]=((baza[2][1]*baza[1][1])%mod+(baza[2][2]*baza[2][1])%mod)%mod;
            aux[2][2]=((baza[2][1]*baza[1][2])%mod+(baza[2][2]*baza[2][2])%mod)%mod;
            baza[1][1]=aux[1][1];
            baza[1][2]=aux[1][2];
            baza[2][1]=aux[2][1];
            baza[2][2]=aux[2][2];
        }
    }
    printf("%lld",rez[2][2]);
}
int main (){
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    long long n;
    scanf("%lld",&n);
    baza[1][2]=baza[2][1]=baza[2][2]=1;
    expo(n-1);
    return 0;
}