#include <cstdio>

using namespace std;

const int mod =  666013;

int k;
long long mat[3][3],rzv[3][3],c[3][3];

int main()
{
    freopen("kfib.in", "r", stdin);
    freopen("kfib.out", "w", stdout);
    scanf("%d", &k);

    rzv[1][1] = rzv[2][2] = 1;
    mat[1][2] = mat[2][1] = mat[2][2] = 1;

    if(k == 0)
        printf("0\n");
    else if(k < 3)
        printf("1\n");
    else
    {
        -- k;

        while(k)
        {
            if(k % 2)
            {
                c[1][1] = mat[1][1] * rzv[1][1] + mat[1][2] * rzv[2][1];
                c[1][2] = mat[1][1] * rzv[1][2] + mat[1][2] * rzv[2][2];
                c[2][1] = mat[2][1] * rzv[1][1] + mat[2][2] * rzv[2][1];
                c[2][2] = mat[2][1] * rzv[1][2] + mat[2][2] * rzv[2][2];
                rzv[1][1] = c[1][1] % mod;
                rzv[1][2] = c[1][2] % mod;
                rzv[2][1] = c[2][1] % mod;
                rzv[2][2] = c[2][2] % mod;
            }
            c[1][1] = mat[1][1] * mat[1][1] + mat[1][2] * mat[2][1];
            c[1][2] = mat[1][1] * mat[1][2] + mat[1][2] * mat[2][2];
            c[2][1] = mat[2][1] * mat[1][1] + mat[2][2] * mat[2][1];
            c[2][2] = mat[2][1] * mat[1][2] + mat[2][2] * mat[2][2];
            mat[1][1] = c[1][1] % mod;
            mat[1][2] = c[1][2] % mod;
            mat[2][1] = c[2][1] % mod;
            mat[2][2] = c[2][2] % mod;
            k /= 2;
        }

        printf("%d\n", rzv[2][2]);
    }

    return 0;
}