#include <fstream>
#define int long long
#define cin fin
#define cout fout

using namespace std;

ifstream cin("kfib.in");
ofstream cout("kfib.out");

struct matrix
{
    int mat[3][3];
    int n, m;
};

matrix fib, a, id;
const int MOD = 666013;
matrix inm(matrix a, matrix b)
{
    matrix rez;
    rez.n = a.n, rez.m = b.m;
    for(int i = 0; i < a.n; i++)
         for(int j = 0; j < b.m; j++)
         {
             rez.mat[i][j] = 0;
             for(int k = 0; k < a.n; k++)
                 rez.mat[i][j] = (rez.mat[i][j] + (a.mat[i][k] * b.mat[k][j] % MOD)) % MOD;
         }

    return rez;
}

matrix put(matrix n, int k)
{
    if(k == 0)
        return id;
    if(k % 2 == 1)
        return inm(put(inm(n, n), k / 2), n);
    return put(inm(n, n), k / 2);
}

signed main()
{
    int k;
    cin>>k;
    if(k == 0 || k == 1)
    {
        cout<<1;
        return 0;
    }
    a.mat[0][0] = 0, a.mat[0][1] = 1, a.mat[1][0] = 1, a.mat[1][1] = 1;
    a.n = 2, a.m = 2;
    fib.mat[0][0] = 1, fib.mat[1][0] = 1;
    fib.n = 2, fib.m = 1;
    id.mat[0][0] = 1, id.mat[1][1] = 1;
    id.n = 2, id.m = 2;

    matrix rez = inm(put(a, k - 1), fib);
    cout<<rez.mat[0][0];
    return 0;
}