#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))
//#pragma GCC optimize("O3")
using namespace std;
using namespace __gnu_pbds;
auto random_address = [] { char *p = new char; delete p; return uint64_t(p); };
const uint64_t SEED = chrono::steady_clock::now().time_since_epoch().count() * (random_address() | 1);
mt19937_64 rng(SEED);
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
ll n;
const ll mod=666013;
ll mat[5][5],rez[5][5],aux[5][5];
bool use;
void inmultmat()
{
    for(int i=1;i<=2;i++)
        for(int j=1;j<=2;j++)
            aux[i][j]=0;
    for(int i1=1;i1<=2;i1++)
        for(int j2=1;j2<=2;j2++)
            for(int k=1;k<=2;k++)
                aux[i1][j2]=(aux[i1][j2]+mat[i1][k]*rez[k][j2])%mod;
    for(int i=1;i<=2;i++)
        for(int j=1;j<=2;j++)
            mat[i][j]=aux[i][j];
}
void inmultrez()
{
    for(int i=1;i<=2;i++)
        for(int j=1;j<=2;j++)
            aux[i][j]=0;
    for(int i1=1;i1<=2;i1++)
        for(int j2=1;j2<=2;j2++)
            for(int k=1;k<=2;k++)
                aux[i1][j2]=(aux[i1][j2]+rez[i1][k]*rez[k][j2])%mod;
    for(int i=1;i<=2;i++)
        for(int j=1;j<=2;j++)
            rez[i][j]=aux[i][j];
}
void pw()
{
    while(n)
    {
        if(n%2==1)
        {
            if(use==0)
            {
                for(int i=1;i<=2;i++)
                    for(int j=1;j<=2;j++)
                        mat[i][j]=rez[i][j];
                use=1;
            }
            else
                inmultmat();
        }
        inmultrez();
        n/=2;
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(0);
    fout.tie(0);
    fin>>n;
    if(n<=1)
    {
        fout<<n;
        return 0;
    }
    rez[1][1]=0;
    rez[1][2]=1;
    rez[2][1]=1;
    rez[2][2]=1;
    pw();
    for(int i=1;i<=2;i++)
        for(int j=1;j<=2;j++)
        {
            rez[i][j]=mat[i][j];
            mat[i][j]=0;
        }
    mat[1][1]=0;
    mat[1][2]=1;
    inmultmat();
    fout<<mat[1][1];
    return 0;
}