#include <bits/stdc++.h>
#define NMAX 5
#define int int64_t
#define double long double
#define cin fin
#define cout fout
using namespace std;

ifstream fin("iepuri.in");
ofstream fout("iepuri.out");
const int mod = 666013;
struct matrix {
    int values[NMAX][NMAX];
    matrix() {
        memset(values, 0, sizeof(values));
    }
    friend matrix operator*(matrix);
    void construct(int n)
    {
        int i;
        for(i=0;i<n;i++)
            values[i][i]=1;
    }
};

matrix operator*(matrix a, matrix b)
{
    matrix ans;
    for (int i = 0; i < NMAX; i++)
        for (int j = 0; j < NMAX; j++)
            for (int k = 0; k < NMAX; k++)
                ans.values[i][j] = (ans.values[i][j] + (1LL * a.values[i][k] * b.values[k][j])%mod)%mod;
    return ans;
}
matrix iNmax;

matrix logPow(matrix x, int n)
{
    if (!n) return iNmax;
    if (n & 1) return x * logPow(x * x, n >> 1);
    return logPow(x * x, n >> 1);
}
int32_t main()
{
    iNmax.construct(5);
    
    int t;
    cin>>t;
       matrix m;
        int x,y,z;
        int a,b,c;
        int zile;
        m.values[0][0]=1;
        m.values[0][1]=1;
        m.values[1][0]=1;
        m.values[2][1]=1;
        
        m=logPow(m,t-2);
        cout<<(m.values[0][0]* 1+ m.values[0][1]) %mod;   




    return 0;
}