#include <bits/stdc++.h>
using namespace std;

class matrixExponentiation
{
private:
#define uint unsigned int
#define lld long long
#define MATRIX_EXPONENTIATION_CHECK_CREATED(ret) if (!created) return ret
#define MATRIX_EXPONENTIATION_ERROR -1
    struct matrix
    {
        vector<vector<int>>m;
        matrix() {}
        void create(uint n)
        {
            m.resize(n);
            for (uint i=0; i<n; ++i)
                m[i].resize(n,0);
        }
    };
    matrix mul(matrix a, matrix b)
    {
        matrix ans;
        ans.create(n);
        for (uint k=0; k<n; ++k)
            for (uint i=0; i<n; ++i)
                for (uint j=0; j<n; ++j)
                    ans.m[i][j] = (ans.m[i][j] + 1LL*a.m[i][k]*b.m[k][j]) % mod;
        return ans;
    }
    matrix logExponentiation(matrix m, lld n)
    {
        if (!n) return iN;
        if (n&1)
            return mul(m,logExponentiation(mul(m,m),n>>1));
        return logExponentiation(mul(m,m), n>>1);
    }
    lld mod;
    uint n;
    bool created;
    matrix reccurence, iN, base;
public:
    matrixExponentiation(): created(false), n(0) {}
    bool create(uint n, lld mod)
    {
        if (created) return false;
        this->n = n;
        this->mod = mod;
        created = true;
        reccurence.create(n);
        iN.create(n);
        base.create(n);
        for (uint i=1; i<n; ++i)
            reccurence.m[i][i-1] = 1;
        for (uint i=0; i<n; ++i)
            iN.m[i][i] = 1;
        return true;
    }
    bool setReccurenceTerm(uint poz, int val)
    {
        MATRIX_EXPONENTIATION_CHECK_CREATED(MATRIX_EXPONENTIATION_ERROR);
        base.m[0][poz] = val;
        return true;
    }
    bool setBaseTerm(uint poz, int val)
    {
        MATRIX_EXPONENTIATION_CHECK_CREATED(MATRIX_EXPONENTIATION_ERROR);
        reccurence.m[0][poz] = val;
        return true;
    }
    lld calculateReccurence(lld nterm)
    {
        MATRIX_EXPONENTIATION_CHECK_CREATED(MATRIX_EXPONENTIATION_ERROR);
        matrix exp = logExponentiation(reccurence, nterm);
        matrix ans = mul(exp, base);
        return ans.m[0][0];
    }
};

int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    lld n;
    cin>>n;
    if (n == 0)
    {
        cout<<"0\n";
        return 0;
    }
    if (n <= 2)
    {
        cout<<"1\n";
        return 0;
    }
    matrixExponentiation fibo;
    fibo.create(2, 666013);
    fibo.setBaseTerm(0, 1);
    fibo.setBaseTerm(1, 1);
    fibo.setReccurenceTerm(0,1);
    fibo.setReccurenceTerm(1,1);
    cout<<fibo.calculateReccurence(n-1)<<'\n';
    return 0;
}