#include <fstream>
#define ll long long
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
const int mod=666013;
ll a[4][4],b[4][4],s[4][4],k;
void inmulteste(ll s[4][4],ll a[4][4],ll b[4][4])
{
    ll i,j,k;
    for(i=1;i<=2;i++)
        for(j=1;j<=2;j++)
            for(k=1;k<=2;k++)
                s[i][j]=(s[i][j]+a[i][k]*b[k][j])%mod;

}
void lgput(ll k)
{
    ll i;
    for(i=1;i<=k;i<<=1)
    {
        if(i&k)
        {
            for(ll j=1;j<=2;j++)
                for(ll l=1;l<=2;l++)
                        s[j][l]=0;
            inmulteste(s,a,b);
            for(ll j=1;j<=2;j++)
                for(ll l=1;l<=2;l++)
                       a[j][l]=s[j][l];
        }
            for(ll j=1;j<=2;j++)
                for(ll l=1;l<=2;l++)
                        s[j][l]=0;
            inmulteste(s,b,b);
            for(ll j=1;j<=2;j++)
                for(ll l=1;l<=2;l++)
                       b[j][l]=s[j][l];
    }
}
int main()
{
    f>>k;
    b[1][1]=b[1][2]=b[2][1]=1;
    a[1][1]=a[2][2]=1;
    lgput(k-1);
    g<<a[1][1];
    return 0;
}