#include <bits/stdc++.h>
#define FILES freopen("kfib.in","r",stdin);\
              freopen("kfib.out","w",stdout);
#define ll long long
#define fastio ios_base::sync_with_stdio(NULL),cin.tie(NULL),cout.tie(NULL);
#define MAX 100000
#define pb push_back
#define mp make_pair
#define mod 666013
#define int ll
using namespace std;
int n,dp[5][5],dp2[5][5];
void Multiply(int A[5][5],int B[5][5])
{
    int new_dp[5][5] = {0};
    for(int i = 1;i <= 3; ++i)
    {
        for(int j = 1;j <= 3; ++j)
        {
            for(int k = 1;k <= 3; ++k){

                new_dp[i][j] = (new_dp[i][j] + A[i][k] * B[k][j]) % mod;
            }
        }
    }
    for(int i = 1;i <= 3; ++i)
        for(int j = 1;j <= 3; ++j) A[i][j] = new_dp[i][j];
}
void fast_exp(int exp)
{
    while(exp)
    {
        if(exp & 1) Multiply(dp,dp2);
        exp >>= 1;
        Multiply(dp2,dp2);
    }
}
signed main()
{
    fastio
    FILES
    cin >> n;
    dp2[1][2] = dp2[2][1] = dp2[2][3]  = dp[1][2] = dp[1][3] = dp2[1][1] = 1;
    dp[1][1] = 2;
    fast_exp(n-3);
    cout << dp[1][1];
}