#include <bits/stdc++.h>

using namespace std;
 long long a[3][3],n[3][3];
 int i,j,k,q;
void multiply(long long  a[3][3],long long  b[3][3])
{
    int c[3][3];
     for(i=1;i<=2;i++)
        for(j=1;j<=2;j++)
        c[i][j]=0;
    for(i=1;i<=2;i++)
        for(j=1;j<=2;j++)
        for(q=1;q<=2;q++)
        c[i][j]+=(a[i][q]*b[q][j])%666013;
    for(i=1;i<=2;i++)
        for(j=1;j<=2;j++)
        a[i][j]=c[i][j]%666013;
}
void pow(long long  a[3][3],int  k,long long  n[3][3])
{
    while(k)
    {
        if(k%2)
        {
            multiply(n,a);
            k--;
        }
        multiply(a,a);
        k/=2;
    }
}
int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    scanf("%d",&k);
    a[1][1]=0;
    a[2][1]=1;
    a[1][2]=1;
    a[2][2]=1;
    n[1][1]=1;
    n[1][2]=0;
    n[2][1]=0;
    n[2][2]=1;


    pow(a,k-1,n);
    printf("%lld",(n[1][1]+n[2][1])%666013);
    return 0;
}