#include <fstream>

using namespace std;
ifstream cin("kfib.in");
ofstream cout("kfib.out");
const int MOD = 666013;
int n, a[2][2], M[2][2];
void inmulmat(int a[2][2], int b[2][2])
{
    int aux[2][2] = {};
    for(int i=0; i<2; i++)
        for(int j=0; j<2; j++)
            for(int k=0; k<2; k++)
                aux[i][j] = (aux[i][j] + (1LL * a[i][k] * b[k][j]) % MOD) % MOD;
    for(int i=0; i<2; i++)
        for(int j=0; j<2; j++)
            a[i][j] = aux[i][j];
}
void fastpow(int p)
{
    while(p)
    {
        if(p % 2)
            inmulmat(M, a);
        inmulmat(a, a);
        p /= 2;
    }
}
int main()
{
    cin >> n;
    a[0][0] = 0;
    a[1][0] = a[0][1] = a[1][1] = 1;
    M[0][1] = M[0][0] = 1;
    M[1][0] = M[1][1] = 0;
    fastpow(n-1);
    cout << M[0][0];
    return 0;
}