#include <bits/stdc++.h>
#define MOD 666013
using namespace std;

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

int n;
long long a[2][2] = {{1, 1}, {1, 0}}, i2[2][2]={{1, 0}, {0, 1}};

void produs(long long x[2][2], long long y[2][2])
{
    int rez[2][2];
    rez[0][0] = (x[0][0] * y[0][0] + x[0][1] * y[1][0])%MOD;
    rez[0][1] = (x[0][0] * y[0][1] + x[0][1] * y[1][1])%MOD;
    rez[1][0] = (x[1][0] * y[0][0] + x[1][1] * y[1][0])%MOD;
    rez[1][1] = (x[1][0] * y[0][1] + x[1][1] * y[1][1])%MOD;
    x[0][0] = rez[0][0];
    x[0][1] = rez[0][1];
    x[1][0] = rez[1][0];
    x[1][1] = rez[1][1];
}

int main()
{
    fin>>n;
    n--;
    while(n)
    {
        if(n%2 == 1)
            produs(i2, a);
        produs(a, a);
        n/=2;
    }
    fout<<i2[0][0];
    return 0;
}