#include <stdio.h>
#include <iostream>
#include <cstring>
#define lld long long
#define MOD 666013
using namespace std;
struct mat
{
    lld v[2][2];
    mat()
    {
        memset(v, 0, sizeof(v));
    }
};
int n;
mat i2;
mat init;
mat inm(mat a, mat b)
{
    mat ans;
    for (int i=0;i<2;++i)
    {
        for (int j=0;j<2;++j)
        {
            for (int k=0;k<2;++k)
            {
                ans.v[i][j] = (ans.v[i][j] + a.v[i][k] * b.v[k][j]) % MOD;
            }
        }
    }
    return ans;
}
mat lowPow(mat a, int n)
{
    if (!n)
    {
        return i2;
    }
    mat ans;
    if (n&1)
    {
        ans = inm(a, lowPow(inm(a, a), n>>1));
    }
    else
    {
        ans = lowPow(inm(a, a), n>>1);
    }
    return ans;
}
int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    cin>>n;
    if (n<=1)
    {
        cout<<n<<'\n';
    }
    else
    {
        i2.v[0][0] = i2.v[1][1] = 1;
        init.v[0][0] = init.v[0][1] = init.v[1][0] = 1;
        mat m = lowPow(init, n-1);
        mat d;
        d.v[0][0] = 1;
        d = inm(m, d);
        cout<<d.v[0][0]<<'\n';
    }
    return 0;
}