#include <cstdio>
#include <algorithm>
#include <cstring>

#define MOD 666013

using namespace std;

class Matrix{
private:
    long long a[2][2];
public:
    Matrix(){
        memset(a,0,sizeof(a));
    }
    Matrix(int _a,int _b,int _c,int _d){
        a[0][0] = _a;
        a[0][1] = _b;
        a[1][0] = _c;
        a[1][1] = _d;
    }
    void Afish(){
        printf("%d\n",(a[0][0]+MOD)%MOD);
    }
    friend Matrix operator *(Matrix A, Matrix B){
        Matrix C;
        for(int i = 0; i <= 1; ++i)
            for(int j = 0; j <= 1; ++j)
                for(int k = 0; k <= 1; ++k)
                    C.a[i][j] = (C.a[i][j] + A.a[i][k] * B.a[k][j])%MOD;
        return C;
    }
};

Matrix lg_put(Matrix A,int b){
    Matrix x1,x2;
    x1 = A;
    x2 = Matrix(1,0,0,1); /// I2
    if(b == 0) return x2;
    if(b == 1) return x1;
    while(b > 1)
        if(b & 1){
            b ^= 1;
            x2 = x1 * x2;
        }
        else{
            b >>=1;
            x1 = x1 * x1;
        }
    return x1 * x2;
}

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

    Matrix A(1,1,1,0);
    int K;
    scanf("%d",&K);
    if( K == 0 )
        printf("0 ");
    else
    {
        A = lg_put(A,K - 1);
        A.Afish();
    }

    return 0;
}