#include <bits/stdc++.h>
#define mod 666013

using namespace std;
ifstream fin ("kfib.in");
ofstream fout ("kfib.out");
struct matrix
{
    int n,m;
    vector< vector<long long> > a;
    matrix(int n, int m)
    {
        this->n=n;
        this->m=m;
        a.resize(n, vector<long long>(m, 0));
    }
    matrix(){}
    matrix operator*(matrix b)
    {
        matrix c(n, b.m);
        for(int i=0;i<c.n;i++)
            for(int j=0;j<c.m;j++)
            {
                for(int k=0;k<m;k++)
                {
                    c.a[i][j]+=(a[i][k]*b.a[k][j])%mod;
                    c.a[i][j]%=mod;
                }

            }

        return c;
    }
    void repr()
    {
        cout<<n<<' '<<m<<'\n';
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
                cout<<a[i][j]<<' ';
            cout<<'\n';
        }
    }
};
matrix identity(int n, int m)
{
    int s=m;
    matrix ans(s, s);
    for(int i=0;i<m;i++)
        ans.a[i][i]=1;

    return ans;
}
matrix put(matrix baza, long long exp)
{
    if(exp==0)
        return identity(baza.n, baza.m);

    if(exp==1)
        return baza;

    matrix ans=put(baza, exp/2);
    ans=ans*ans;

    if(exp%2)
        return ans*baza;
    else
        return ans;
}
int k;
int main()
{

    fin>>k;
    matrix s(1, 2);
    s.a[0][0]=0;
    s.a[0][1]=1;

    matrix fib(2, 2);
    fib.a[0][0]=0;
    fib.a[0][1]=1;
    fib.a[1][0]=1;
    fib.a[1][1]=1;

    s=s*put(fib, k);

    fout<<s.a[0][0];
    return 0;
}