#include <iostream>

using namespace std;

const int M = 666013;
long long d[3][3],p[3][3];

void produs(long long a[3][3],long long b[3][3])
{
    int i,j,k;
    long long aux[3][3];
    for(i=0;i<3;i++)
    {
        for(j=0;j<3;j++)
        {
            aux[i][j]=0;
            for(k=0;k<3;k++)
            {
                aux[i][j]+=a[i][k]*b[k][j];
                aux[i][j] %= M;
            }
        }
    }
    for(i=0;i<3;i++)
    {
        for(j=0;j<3;j++)
        {
            a[i][j]=aux[i][j];
        }
    }
}
int main()
{
    int n;
    p[0][0]=p[1][1]=p[2][2]=1;
    d[0][0]=d[0][1]=d[1][0]=d[2][1]=1;
    cin>>n;
    n-=2;
    while(n!=0)
    {
        if(n%2!=0)
            produs(p,d);
        produs(d,d);
        n/=2;
    }
    cout<<(p[0][1]+p[0][0])%M;
}