#include <bits/stdc++.h>

using namespace std;

#define MOD 666013
#define ll long long

struct mat{
    ll a[2][2];
    inline mat operator*(mat b){
        mat x;
        int i,j,k;
        for (i=0;i<2;i++)
            for (j=0;j<2;j++) x.a[i][j]=0;
        for (i=0;i<2;i++)
            for (j=0;j<2;j++)
                for (k=0;k<2;k++)
                    x.a[i][j]=(x.a[i][j]+a[i][k]*b.a[k][j])%MOD;
        return x;
    }
}c,t,i2;

ll k;


mat ptr(mat p, int n){
    if (n==1) return p;
    if (n==0) return i2;
    mat x=ptr(p,n/2);
    x=x*x;
    if (n%2) x=x*p;
    return x;
}

/*void afis(mat p){
    int i,j;
    for (i=0;i<2;i++){
        for (j=0;j<2;j++){
            printf("%lld ",p.a[i][j]);
        }
        printf("\n");
    }
}*/

int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);

    scanf("%lld",&k);
    c.a[0][0]=0;c.a[0][1]=1;c.a[1][0]=1;c.a[1][1]=1;
    t.a[0][0]=0;t.a[0][1]=1;t.a[1][0]=0;t.a[1][1]=0;
    i2.a[0][0]=1;i2.a[0][1]=0;i2.a[1][0]=0;i2.a[1][1]=1;
    c=ptr(c,k);
    t=t*c;
    printf("%lld",t.a[0][0]);
    return 0;
}