#include <fstream>
#define MOD 666013
using namespace std; 
void mult_mat(long long m1[2][2], long long m2[2][2]) {
long long res[2][2];
res[0][0] = (m1[0][0] * m2[0][0] + m1[0][1] * m2[1][0]) % MOD;
res[0][1] = (m1[0][0] * m2[0][1] + m1[0][1] * m2[1][1]) % MOD;
res[1][0] = (m1[1][0] * m2[0][0] + m1[1][1] * m2[1][0]) % MOD;
res[1][1] = (m1[1][0] * m2[0][1] + m1[1][1] * m2[1][1]) % MOD;
m1[0][0] = res[0][0];
m1[0][1] = res[0][1];
m1[1][0] = res[1][0];
m1[1][1] = res[1][1];
}void expo(long long res[2][2], long long m[2][2], long long n)
{
long long c = 1;
res[0][0] = 1;
res[0][1] = 0;
res[1][0] = 0;
res[1][1] = 1; 
while (true) {
if (c & n) {
mult_mat(res, m);
}
mult_mat(m, m);
c = c << 1;
if (c > n)
break;
}
}
int main(void)
{
ifstream f("kfib.in");
long long k;
f >> k; 
f.close(); 
long long m[2][2] = {{0, 1}, {1, 1}};
long long res[2][2];
expo(res, m, k);
ofstream g("kfib.out");
g << res[1][0] << endl;
g.close();
}