#include <cstdio>
#define mod 666013

using namespace std;

long long n,a[5][5],b[5][5],c[5][5];

long long copiere(long long a[5][5],long long b[5][5])
{
    a[1][1]=b[1][1]%mod;
    a[1][2]=b[1][2]%mod;
    a[2][2]=b[2][2]%mod;
    a[2][1]=b[2][1]%mod;
}

void inmultire(long long a[5][5],long long b[5][5],long long c[5][5])
{
    c[1][1]=((a[1][1]*b[1][1])%mod+(a[1][2]*b[2][1])%mod)%mod;
    c[1][2]=((a[1][1]*b[1][2])%mod+(a[1][2]*b[2][2])%mod)%mod;
    c[2][1]=((a[2][1]*b[1][1])%mod+(a[2][2]*b[2][1])%mod)%mod;
    c[2][2]=((a[2][1]*b[1][2])%mod+(a[2][2]*b[2][2])%mod)%mod;
}

void ridicare(long long n,long long m[5][5])
{
    if(n>1)
    {
        ridicare(n/2,m);
        inmultire(m,m,c);
        copiere(m,c);
        if(n%2==1)
        {
            inmultire(m,a,c);
            copiere(m,c);
        }
    }
    else
        copiere(m,a);
}

int main()
{
    long long m[5][5];
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    scanf("%d",&n);
    n++;
    a[1][1]=0;
    a[1][2]=a[2][1]=a[2][2]=1;
    ridicare(n,m);
    printf("%d\n",m[1][1]);
    return 0;
}