#include <cstdio>
#define MOD 666013
#define fin "kfib.in"
#define fout "kfib.out"
#define ll long long
#define f(i) for(int i =0;i<=1;++i)
using namespace std;
ll k,i,j;
void inmult(ll a[2][2],ll b[2][2],ll c[2][2])
{
    f(i)
    {
        f(j)
            {
                c[i][j]=0;
                f(k)
                {
                    c[i][j] += a[i][k]*b[k][j];
                    c[i][j]=c[i][j]%MOD;
                }
            }
    }
}
void cop(ll a[2][2], ll b[2][2])
{
    f(i)
    {
        f(j)
            a[i][j]=b[i][j];
    }
}
int main()
{
    freopen(fin,"r",stdin);
    freopen(fout,"w",stdout);
    ll a[2][2]={{1,1}, {1,0} };
    ll b[2][2]={{1,0}, {1,0} };
    ll c[2][2];
    scanf("%lld",&k);
    --k;
    while(k)
    {
        if(k%2)
        {
            inmult(b,a,c);
            cop(b,c);
        }
        inmult(a,a,c);
        cop(a,c);
        k/=2;
    }
    printf("%lld",b[0][0]%MOD);

    return 0;
}