#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
#define MOD 666013
void mul(int a[2][2], int b[2][2])
{
    int c[2][2];
    int i, j, k;
    for(i = 0 ; i < 2 ; i++)
    {
        for(j = 0 ; j < 2 ; j++)
        {
            c[i][j] = 0;
            for(k = 0 ; k < 2 ; k++)
            {
                c[i][j] = (1ll * c[i][j] + 1ll * a[i][k] * b[k][j]) % MOD;
            }
        }
    }
    for(i = 0 ; i < 2 ; i++)
        for(j = 0 ; j < 2 ; j++)
            a[i][j] = c[i][j];
}

int pow(int a[2][2], int p)
{
    int rez[2][2] = {{1, 0}, {0, 1}};

    while(p)
    {
        if(p & 1)
        {
            mul(rez, a);
        }
        //cout << a[0][0] << " " << a[0][1] << "\n" << a[1][0] << " " << a[1][1] << "\n\n";
        p >>= 1;
        mul(a, a);
    }
    return rez[0][0];
}

int main()
{
    int n, a[2][2] = {0};
    fin >> n;
    if(n <= 1)
    {
        fout << n << "\n";
        return 0;
    }
    a[0][0] = a[1][0] = a[0][1] = 1;

    fout << pow(a, n - 1) << "\n";
}