#include <cstdio>
using namespace std;

const int MODULO = 666013;

struct matrice
{
    long long a11,a12;
    long long a21,a22;

    matrice operator * (matrice &b)
    {
        matrice c;
        long long b11 = b.a11;
        long long b12 = b.a12;
        long long b21 = b.a21;
        long long b22 = b.a22;
        c.a11 = (a11 * b11 + a12 * b21) % MODULO;
        c.a12 = (a11 * b12 + a12 * b22) % MODULO;
        c.a21 = (a21 * b11 + a22 * b21) % MODULO;
        c.a22 = (a21 * b12 + a22 * b22) % MODULO;
        return c;
    }

    matrice operator + (matrice &b)
    {
        matrice c;
        long long b11 = b.a11;
        long long b12 = b.a12;
        long long b21 = b.a21;
        long long b22 = b.a22;
        c.a11 = (a11 + b11) % MODULO;
        c.a12 = (a12 + b12) % MODULO;
        c.a21 = (a21 + b21) % MODULO;
        c.a22 = (a22 + b22) % MODULO;
        return c;
    }
};


int k;


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

matrice putere(matrice a, int b)
{
    if (b <= 0)
        return (matrice){1,0,0,1};
    if (b == 1)
        return a;
    matrice c = putere(a, b / 2);
    if (b % 2 == 0)
        return c * c;
    else return c * c * a;
}

int main()
{
    citire();
    if (k == 0)
    {
        printf("0\n");
        return 0;
    }
    matrice Z;
    Z.a11 = 0; Z.a12 = 1;
    Z.a21 = 1; Z.a22 = 1;
    Z = putere(Z, k - 1);
    printf("%d\n",(int)(Z.a22));
    return 0;
}