#include <fstream>
#include <cstring>
#define MOD 666013
using namespace std;

ifstream fin("kfib.in");
ofstream fout("kfib.out");

int n;
long long sol[2][2]={0,1,0,0}, m[2][2]={0,1,1,1}, aux[2][2], aux1[2][2];

int main()
{
    fin>>n;
    for(int i=1; i<=n; i<<=1)
    {
        if(n&i)
        {
            memcpy(aux, sol, sizeof sol);
            sol[0][0]=((aux[0][0]*m[0][0])%MOD+(aux[0][1]*m[1][0])%MOD)%MOD;
            sol[0][1]=((aux[0][0]*m[0][1])%MOD+(aux[0][1]*m[1][1])%MOD)%MOD;
        }
        memcpy(aux, m, sizeof m);
        memcpy(aux1, m, sizeof m);
        m[0][0]=((aux[0][0]*aux1[0][0])%MOD+(aux[0][1]*aux1[1][0])%MOD)%MOD;
        m[0][1]=((aux[0][0]*aux1[0][1])%MOD+(aux[0][1]*aux1[1][1])%MOD)%MOD;
        m[1][0]=((aux[1][0]*aux1[0][0])%MOD+(aux[1][1]*aux1[1][0])%MOD)%MOD;
        m[1][1]=((aux[1][0]*aux1[0][1])%MOD+(aux[1][1]*aux1[1][1])%MOD)%MOD;
    }
    fout<<sol[0][0];
    return 0;
}