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

using namespace std;

#define Matrix vector< vector<int> >

Matrix operator * (Matrix a,Matrix b)
{
    Matrix ans;
    int r1=a.size(),c1=a[0].size();
    int r2=b.size(),c2=b[0].size();
    if(c1!=r2)
        return ans;
    for(int i=0;i<r1;i++)
    {
        ans.push_back({});
        for(int j=0;j<c2;j++)
        {
            ans[i].push_back(0);
            for(int k=0;k<c1;k++)
            {
                long long F=a[i][k];
                long long S=b[k][j];
                long long sum=(F*S+ans[i][j])%666013;
                ans[i][j]=sum;
            }
        }
    }
    return ans;
}

Matrix Power(Matrix a,int b)
{
    Matrix ans;
    int r=a.size(),c=a[0].size();
    if(r!=c)
        return ans;
    for(int i=0;i<r;i++)
    {
        ans.push_back({});
        for(int j=0;j<c;j++)
            ans[i].push_back((i==j));
    }
    while(b)
    {
        if(b%2)
            ans=ans*a;
        a=a*a;
        b/=2;
    }
    return ans;
}

int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    Matrix a(2);
    a[0].push_back(0); a[0].push_back(1);
    a[1].push_back(1); a[1].push_back(1);
    Matrix Fib(1);
    Fib[0].push_back(0); Fib[0].push_back(1);
    int n;
    cin>>n;
    Matrix ans=Fib*Power(a,n-1);
    cout<<ans[0][1]<<"\n";
    return 0;
}