#include <fstream>
#define int long long

using namespace std;
ifstream cin("kfib.in");
ofstream cout("kfib.out");
const int mod = 666013;
int n;
struct idt
{
    int mat[2][2]={0};
};
idt identica;
idt mul(idt a,idt b)
{
    idt ans;
    for(int i=0;i<2;i++)
    {
        for(int j=0;j<2;j++)
        {
            ans.mat[i][j]=0;
            for(int x=0;x<2;x++)
            {
                ans.mat[i][j]+=1LL*a.mat[i][x]*b.mat[x][j]%mod;
                if(ans.mat[i][j]>=mod)
                    ans.mat[i][j]-=mod;
            }
        }
    }
    return ans;
}
idt xlan(idt a,int n)
{
    if(n==0) return identica;
    else
    {
        idt p=xlan(a,n/2);
        if(n%2==0)
            return mul(p,p);
        else
            return mul(mul(p,p),a);
    }
}
signed main()
{
    cin>>n;
    idt a;
    a.mat[0][0]=1; a.mat[0][1]=1; a.mat[1][0]=1; a.mat[1][1]=0;
    identica={1,0,0,1};
    cout<<xlan(a,n).mat[0][1];
    return 0;
}