#include <bits/stdc++.h>
using namespace std;
struct matrix
{
    int m1[3][3];
};
matrix inmult(matrix a,matrix b)
{
    matrix ans;
    int i,j;
    for(i=1;i<=2;i++)
        for(j=1;j<=2;j++)
    {
        ans.m1[i][j]=0;
        for(int p=1;p<=2;p++)
        {
            long long res=1LL*a.m1[i][p]*b.m1[p][j];
            res%=666013;
            ans.m1[i][j]+=res;
            ans.m1[i][j]%=666013;
        }
    }
    return ans;
}
matrix in1(matrix a,int p)
{
    matrix ans;
    ans.m1[1][1]=1;
    ans.m1[2][2]=1;
    ans.m1[1][2]=0;
    ans.m1[2][1]=0;
    while(p)
    {
        if(p&1)ans=inmult(ans,a);
        a=inmult(a,a);
        p=p/2;
    }
    return ans;
}
int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    int n;
    scanf("%d",&n);
    if(n==0)
    {
        printf("0");
        return 0;
    }
    if(n==1)
    {
        printf("1");
        return 0;
    }
    if(n==2)
    {
        printf("1");
        return 0;
    }
    matrix ans;
    ans.m1[1][2]=1;
    ans.m1[2][1]=1;
    ans.m1[2][2]=1;
    ans.m1[1][1]=0;
    ans=in1(ans,n);
    printf("%d\n",ans.m1[1][2]);
    return 0;
}