#include <fstream>
#define mo 666013
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
long long z[3][3],rz[3][3],c[3][3];
int n;
void inm(long long a[3][3],long long b[3][3])
{
    c[0][0]=(a[0][0]%mo*b[0][0]%mo)%mo+(a[0][1]%mo*b[1][0]%mo)%mo;
    c[0][1]=(a[0][0]%mo*b[0][1]%mo)%mo+(a[0][1]%mo*b[1][1]%mo)%mo;
    c[1][0]=(a[1][0]%mo*b[0][0]%mo)%mo+(a[1][1]%mo*b[1][0]%mo)%mo;
    c[1][1]=(a[1][0]%mo*b[0][1]%mo)%mo+(a[1][1]%mo*b[1][1]%mo)%mo;
}
void calc(long long a[3][3],long long b[3][3],int p)
{
    int i,j;
    if (p>1)
    {
        if (p%2==0)
        {
            calc(a,b,p/2);
            inm(a,a);
            for (i=0;i<=1;i++)
                for (j=0;j<=1;j++)
                a[i][j]=c[i][j];
        }
        else
        {
            calc(a,b,p-1);
            inm(a,b);
            for (i=0;i<=1;i++)
                for (j=0;j<=1;j++)
                a[i][j]=c[i][j];
        }
    }
}
int main ()
{
    f>>n;
    z[0][1]=z[1][0]=z[1][1]=rz[0][1]=rz[1][0]=rz[1][1]=1;
    calc(rz,z,n);
    g<<rz[0][1];
    return 0;
}