#include <bits/stdc++.h>
#define mod 666013
#define ll long long
using namespace std;
ifstream fin ("kfib.in");
ofstream fout ("kfib.out");
ll k;
struct mat
{
    ll m[2][2];
};
mat mat1={
    1,0,
    0,1
};
mat mat2={
    1,1,
    1,0
};
mat inmultire (mat x, mat y)
{
    mat a;
    a.m[0][0]=(x.m[0][0]*y.m[0][0]+x.m[0][1]*y.m[1][0])%mod;
    a.m[0][1]=(x.m[0][0]*y.m[0][1]+x.m[0][1]*y.m[1][1])%mod;
    a.m[1][0]=(x.m[1][0]*y.m[0][0]+x.m[1][1]*y.m[1][0])%mod;
    a.m[1][1]=(x.m[1][0]*y.m[0][1]+x.m[1][1]*y.m[1][1])%mod;
    return a;
}
mat lgput (mat m, ll k)
{
    if (k==0)
        return mat1;
    if (k%2==0)
        return lgput (inmultire (m, m), k/2);
    return inmultire (m, lgput (inmultire (m, m), k/2));
}
int main()
{
    fin >> k;
    fout<<lgput (mat2, k).m[0][1];
    return 0;
}