#include<fstream>
using namespace std;

ifstream cin("kfib.in");
ofstream cout("kfib.out");

#define ll long long
#define mod 666013

const int m[1][2]={0,1};

ll k;

ll mult(ll a, ll b)
{
    return ((a%mod)*(b%mod))%mod;
}
int main()
{
    int z[2][2]; z[0][0]=0; z[0][1]=z[1][0]=z[1][1]=1;
    cin>>k;
    ll n=k;
    ll res[2][2];
    res[0][0]=res[1][1]=1;
    res[0][1]=res[1][0]=0;
    while (n)
    {
        if (n%2==1)
        {
            n--;
            ll aux[2][2];
            aux[0][0]=mult(res[0][0],z[0][0])+mult(res[0][1],z[1][0]);
            aux[0][1]=mult(res[0][0],z[0][1])+mult(res[0][1],z[1][1]);
            aux[1][0]=mult(res[1][0],z[0][0])+mult(res[1][1],z[1][0]);
            aux[1][1]=mult(res[1][0],z[0][1])+mult(res[1][1],z[1][1]);
            int i,j;
            for (i=0;i<2;i++)
               for (j=0;j<2;j++)
                 res[i][j]=aux[i][j];

        }
        n/=2;
        int aux[2][2];
        aux[0][0]=mult(z[0][0],z[0][0])+mult(z[0][1],z[1][0]);
        aux[0][1]=mult(z[0][0],z[0][1])+mult(z[0][1],z[1][1]);
        aux[1][0]=mult(z[0][0],z[1][0])+mult(z[1][1],z[1][0]);
        aux[1][1]=mult(z[1][0],z[0][1])+mult(z[1][1],z[1][1]);
        int i,j;
        for (i=0;i<2;i++)
               for (j=0;j<2;j++)
                 z[i][j]=aux[i][j];
    }
    int sol[2][2];
    sol[0][0]=mult(m[0][0],res[0][0])+mult(m[0][1],res[1][0]);
    sol[0][1]=mult(m[0][0],res[0][1])+mult(m[0][1],res[1][1]);
    cout<<sol[0][0];
    return 0;

}