#include<stdio.h>
#define mod 666013
struct mat
{
    int m[4][4];

};
mat prod(mat a, mat b)
{
    int i,j,z;
    mat c;
    for(i=1;i<=2;i++)
        for(j=1;j<=2;j++)
        {
            c.m[i][j]=0;
            for(z=1;z<=2;z++)
                c.m[i][j]=(1LL*c.m[i][j]+(1LL*a.m[i][z]*b.m[z][j])%mod)%mod;
        }
    return c;

}
mat lgput(mat a, int k)
{
    if(k==1)
        return a;
    if(k%2==0)
        return lgput(prod(a,a),k/2);
    return prod(a,lgput(prod(a,a),(k-1)/2));
}
int k;
mat sol,e,d;
int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);

    scanf("%d",&k);
    k++;
    e.m[1][1]=1;
    e.m[2][1]=1;
    d.m[1][2]=d.m[2][1]=d.m[2][2]=1;
    sol=prod(e,lgput(d,k));
    printf("%d",sol.m[1][1]);
    return 0;

}