#include <bits/stdc++.h>
 
using namespace std;
 
ifstream fin("kfib.in");
ofstream fout("kfib.out");
 
const int MOD = 666013;
long long mat[3][3], m[3][3];
int n;

void inmultire(long long m1[][3],long long m2[][3])
{
    int i, j, k;
    long long aux[3][3] = {};
    for(i = 1; i <= 2; i++)
        for(j = 1; j <= 2; j++)
            for(k = 1; k <= 2; k++) {
                aux[i][j] += (m1[i][k] * m2[k][j]) % MOD;
            }
    for(i = 1; i <= 2; i++)
        for(j = 1; j <= 2; j++)
            mat[i][j] = aux[i][j] % MOD;
}
 
void putere(int p)
{	
    if(p == 1) {
        for(int i = 1; i <= 2; i++)
            for(int j = 1;j <= 2; j++)
                mat[i][j] = m[i][j];
    }
    else {
        if(p % 2 == 0) {
            putere(p / 2);
            inmultire(mat, mat);
        }
        else {
            putere(p - 1);
            inmultire(m, mat);
        }
    }
}
 
int main()
{
	fin >> n;
	m[2][1] = 1;
	m[1][2] = 1;
	m[2][2] = 1;
    putere(n - 2);
    fout << (mat[1][2]+mat[2][2]) % MOD << '\n';
	return 0;
}