#include <bits/stdc++.h>
#define mod 666013
#define MAX 200000
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define int long long
#define FILES freopen("kfib.in","r",stdin);\
              freopen("kfib.out","w",stdout);
using namespace std;
int n;
class Matrix
{
public:
    int a[10][10] = {0};
    Matrix operator * (Matrix & b)
    {
        Matrix rez;
        for(int i = 1; i <= 3; ++i)
        {
            for(int j = 1; j <= 3; ++j)
            {
                for(int k = 1; k <= 3; ++k)
                    rez.a[i][j] = (rez.a[i][j] + a[i][k] * b.a[k][j]) % mod;
            }
        }
        return rez;
    }
};
Matrix fib, dp;
void exp_rapid(int e)
{
    while(e)
    {
        if(e & 1)
            fib = fib * dp;
        dp = dp * dp;
        e >>= 1;
    }
}
signed main()
{
    fastio
    FILES
    cin >> n;
    fib.a[3][1] = fib.a[3][2] = dp.a[2][1] = dp.a[2][3] = dp.a[3][2] = dp.a[3][3] = 1;
    fib.a[3][3] = 2;
    if(n <= 3)
    {
        cout << fib.a[3][n];
        return 0;
    }
    exp_rapid(n - 3);
    cout << fib.a[3][3];
}