#include <iostream>
#include <vector>
#include <cstdio>

using namespace std;

const int MOD=666013;

int add(int a,int b)
{
        a+=b;
        if(a>=MOD) return a-MOD;
        if(a<0) return a+MOD;
        return a;
}

int mul(int a,int b)
{
        return a*(long long)b%MOD;
}

#define matrix vector <vector <int>>

matrix operator * (matrix a,matrix b)
{
        int n=a.size(),m=a[0].size();
        matrix res;
        res.resize(n);
        for(int j=0;j<n;j++)
        {
                res[j].resize(m,0);
        }
        for(int r=0;r<n;r++)
        {
                for(int c=0;c<m;c++)
                {
                        for(int k=0;k<m;k++)
                        {
                                res[r][c]=add(res[r][c],mul(a[r][k],b[k][c]));
                        }
                }
        }
        return res;
}

matrix power(matrix a,int b)
{
        int n=a.size();
        matrix res;
        res.resize(n);
        for(int i=0;i<n;i++)
        {
                res[i].resize(n,0);
                res[i][i]=1;
        }
        while(b)
        {
                if(b&1)
                {
                        res=res*a;
                }
                a=a*a;
                b>>=1;
        }
        return res;
}

int GetFibo(int n)
{
        matrix init(1); init[0].push_back(0), init[0].push_back(1);
        matrix kol(2); kol[0].push_back(0), kol[0].push_back(1), kol[1].push_back(1), kol[1].push_back(1);
        kol=power(kol,n-1);
        init=init*kol;
        return init[0].back();
}

int main()
{
        freopen("kfib.in","r",stdin);
        freopen("kfib.out","w",stdout);
        int n;
        cin>>n;
        cout<<GetFibo(n)<<"\n";
        return 0;
}