#include <iostream>
#include <cstdio>
using namespace std;
const int MOD=666013;
int maux[2][2]={{0,1},{1,1}};
int m[2][2];
void inmultireMatrici(int m1[2][2],int m2[2][2])
{
    m[0][0]=(m1[0][0]*m2[0][0]%MOD+m1[0][1]*m2[1][0]%MOD)%MOD;
    m[0][1]=(m1[0][0]*m2[0][1]%MOD+m1[0][1]*m2[1][1]%MOD)%MOD;
    m[1][0]=(m1[1][0]*m2[0][0]%MOD+m1[1][1]*m2[1][0]%MOD)%MOD;
    m[1][1]=(m1[1][0]*m2[0][1]%MOD+m1[1][1]*m2[1][1]%MOD)%MOD;
}
void cpy(int m1[2][2],int m2[2][2])
{
    m2[0][0]=m1[0][0];
    m2[0][1]=m1[0][1];
    m2[1][0]=m1[1][0];
    m2[1][1]=m1[1][1];
}
void lgput(int p)
{
    int rez[2][2]={{1,0},{0,1}};
    while(p)
    {
        if(p%2)
            {
                inmultireMatrici(rez,maux);
                cpy(m,rez);
            }
        inmultireMatrici(maux,maux);
        cpy(m,maux);
        p/=2;
    }
    printf("%d",(rez[1][1])%MOD);
}
int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    int n;
    scanf("%d",&n);
    lgput(n-1);
    return 0;
}