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

ifstream fin("kfib.in");
ofstream fout("kfib.out");
int k;
long long a[3][3], b[3][3], c[3][3], rez[3][3];

int main()
{
    fin>>k;
    k--;
    rez[1][1] = rez[2][2] = 1;
    a[1][2] = a[2][1] = a[2][2] = 1;

    while(k)
    {
        if(k%2)
        {
            b[1][1] = rez[1][1];
            b[1][2] = rez[1][2];
            b[2][1] = rez[2][1];
            b[2][2] = rez[2][2];

            c[1][1] = (a[1][1]*b[1][1] + a[1][2]*b[2][1]) % MOD;
            c[1][2] = (a[1][1]*b[1][2] + a[1][2]*b[2][2]) % MOD;
            c[2][1] = (a[2][1]*b[1][1] + a[2][2]*b[2][1]) % MOD;
            c[2][2] = (a[2][1]*b[1][2] + a[2][2]*b[2][2]) % MOD;

            rez[1][1] = c[1][1];
            rez[1][2] = c[1][2];
            rez[2][1] = c[2][1];
            rez[2][2] = c[2][2];
        }

        k /= 2;
        b[1][1] = a[1][1];
        b[1][2] = a[1][2];
        b[2][1] = a[2][1];
        b[2][2] = a[2][2];

        c[1][1] = (a[1][1]*b[1][1] + a[1][2]*b[2][1]) % MOD;
        c[1][2] = (a[1][1]*b[1][2] + a[1][2]*b[2][2]) % MOD;
        c[2][1] = (a[2][1]*b[1][1] + a[2][2]*b[2][1]) % MOD;
        c[2][2] = (a[2][1]*b[1][2] + a[2][2]*b[2][2]) % MOD;

        a[1][1] = c[1][1];
        a[1][2] = c[1][2];
        a[2][1] = c[2][1];
        a[2][2] = c[2][2];
    }

    fout<<rez[2][2];

    fin.close(); fout.close();
    return 0;
}