#include <bits/stdc++.h>

using namespace std;

const int MOD=666013;
#define int long long
vector<vector<int>> mul(vector<vector<int>> A, vector<vector<int>> B)
{
    vector<vector<int>> rez(A.size(), vector<int>(B[0].size(), 0));
    for(int i=0; i<rez.size(); i++)
        for(int j=0; j<rez[i].size(); j++)
            for(int k=0; k<B.size(); k++)
                rez[i][j]=(rez[i][j]+A[i][k]*B[k][j])%MOD;
    return rez;
}
vector<vector<int>> IDN(2, vector<int>(2, 0));

vector<vector<int>> matpow(vector<vector<int>> A, int exp)
{
    vector<vector<int>> rez=IDN;
    while(exp)
    {
        if(exp&1)
            rez=mul(rez, A);
        A=mul(A, A);
        exp>>=1;
    }
    return rez;
}
signed main()
{
    freopen("kfib.in", "r", stdin);
    freopen("kfib.out", "w", stdout);
    IDN[0][0]=IDN[1][1]=1;
    int k;
    cin>>k;
    vector<vector<int>> FIB(2, vector<int>(2, 0));
    FIB[0][0]=FIB[0][1]=FIB[1][0]=1;
    FIB=matpow(FIB, k);
    vector<vector<int>> ANS(2, vector<int>(1, 0));
    ANS[0][0]=1;
    ANS[1][0]=0;
    ANS=mul(FIB, ANS);
    cout<<ANS[1][0];
    return 0;
}