#include <bits/stdc++.h>

using namespace std;

const int mod = 666013;

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

    matrix()
    {
        n = m = 2;
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j)
                mat[i][j] = 0;
    }

    void U()
    {
        n = m = 2;
        for (int i = 1; i <= n; ++i)
            mat[i][i] = 1;
    }

    void init(matrix e)
    {
        n = e.n; m = e.m;
        for (int i = 1; i <= e.n; ++i)
            for (int j = 1; j <= e.m; ++j)
                mat[i][j] = e.mat[i][j];
    }

    matrix operator * (matrix other)
    {
        matrix ret;

        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= other.m; ++j)
                for (int k = 1; k <= m; ++k)
                    ret.mat[i][j] = (1LL * ret.mat[i][j] + 1LL * mat[i][k] * other.mat[k][j]) % mod;

        return ret;
    }
};

int k;
matrix a , b , ans;

matrix lgput(matrix a , int b)
{
    matrix ret , act;
    ret.U(); act.init(a);

    for (int i = 0; (1 << i) <= b; ++i)
    {
        if (b & (1 << i)) ret = ret * act;
        act = act * act;
    }
    return ret;
}

int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);

    scanf("%d", &k);

    a.mat[1][2] = 1; a.n = 1;
    b.mat[1][2] = b.mat[2][1] = b.mat[2][2] = 1;

    ans = a * lgput(b , k);
    printf("%d\n", ans.mat[1][1]);

    return 0;
}