#include <fstream>
#define MOD 666013
using namespace std;
int main()
{
    ifstream in("kfib.in");
    ofstream out("kfib.out");
    long long n;
    long long c[]={0, 1, 1, 1}, r[]={1, 0, 0, 1}, aux[4];
    in>>n;
    --n;
    while(n>0)
    {
        if(n%2)
        {
            aux[0]=r[0];
            aux[1]=r[1];
            aux[2]=r[2];
            aux[3]=r[3];
            r[0]=aux[0]*c[0]+aux[1]*c[2];
            r[1]=aux[0]*c[1]+aux[1]*c[3];
            r[2]=aux[2]*c[0]+aux[3]*c[2];
            r[3]=aux[2]*c[1]+aux[3]*c[3];
            r[0]%=MOD;
            r[1]%=MOD;
            r[2]%=MOD;
            r[3]%=MOD;
        }
        n/=2;
        aux[0]=c[0];
        aux[1]=c[1];
        aux[2]=c[2];
        aux[3]=c[3];
        c[0]=aux[0]*aux[0]+aux[1]*aux[2];
        c[1]=aux[0]*aux[1]+aux[1]*aux[3];
        c[2]=aux[1]*aux[0]+aux[1]*aux[3];
        c[3]=aux[1]*aux[2]+aux[3]*aux[3];
        c[0]%=MOD;
        c[1]%=MOD;
        c[2]%=MOD;
        c[3]%=MOD;
    }
    out<<r[3]<<'\n';
    in.close(); out.close();
    return 0;
}