#include <iostream>
#include <fstream>
#include <vector>
#define int long long
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");

const int MOD=666013;
int k;
using matrix=vector<vector<int>>;

matrix matmul(matrix a, matrix b){
    int n=a.size(), m=b.size(), p=b[0].size();
    matrix rez(a.size(), vector<int>(p, 0));

    for(int i=0;i<n;i++){
        for(int j=0;j<p;j++){
            for(int k=0;k<m;k++){
                rez[i][j]+=a[i][k]*b[k][j];
                rez[i][j]%=MOD;
            }
        }
    }

    return rez;
}

matrix lgpow(matrix b, int e){
    if(e==0){
        matrix iden(b.size(), vector<int>(b.size(), 0));
        for(int i=0;i<b.size();i++)
            iden[i][i]=1;
        return iden;
    }
    if(e%2==0){
        matrix p=lgpow(b, e/2);
        return matmul(p, p);
    }
    return matmul(lgpow(b, e-1), b);
}


signed main()
{
    fin>>k;

    matrix mat={{1, 1}, {1, 0}};

    mat=lgpow(mat, k-2);

    matrix fib(2, vector<int>(1, 1));

    matrix ans=matmul(mat, fib);

    fout<<ans[0][0];


    return 0;
}