#include <cstdio>
#define mod 666013
#define NMAX 100000

using namespace std;

long long a[5][5],p[5][5];
long long x,y,z,w,x1,y1,z1,w1;
int n,k,i;
int b[NMAX];

void transf(int n)
{
    while(n > 0)
    {
        b[++k]=n%2;
        n=n/2;
    }
}

int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    scanf("%d",&n);
    --n;transf(n);
    p[1][1]=1;p[2][2]=1;
    a[1][1]=0;a[1][2]=1;a[2][1]=1;a[2][2]=1;
    for(int i = k; i >= 1; --i)
    {
        x=((p[1][1] * p[1][1])%mod + (p[1][2] * p[2][1])%mod) % mod;
        y=((p[1][1] * p[1][2])%mod + (p[1][2] * p[2][2])%mod) % mod;
        z=((p[2][1] * p[1][1])%mod + (p[2][2] * p[2][1])%mod) % mod;
        w=((p[2][1] * p[1][2])%mod + (p[2][2] * p[2][2])%mod) % mod;
        if (b[i]==1)
        {
            x1=((a[1][1] * x)%mod + (a[2][1]*y)%mod) % mod;
            y1=((a[1][2] * x)%mod + (a[2][2]*y)%mod) % mod;
            z1=((a[1][1] * z)%mod + (a[2][1]*w)%mod) % mod;
            w1=((a[1][2] * z)%mod + (a[2][2]*w)%mod) % mod;
            p[1][1]=x1;p[1][2]=y1;p[2][1]=z1;p[2][2]=w1;
        }
        else
        {
         p[1][1]=x;p[1][2]=y;p[2][1]=z;p[2][2]=w;
        }
    }
    printf("%d\n",p[2][2]);
    return 0;
}