#include <bits/stdc++.h>

using namespace std;
const int MOD=666013;
const int N=2;

// Algoritm pentru determinarea termenului n din șirul fibonacci
void multiply(long long a[N][N], long long b[N][N])
{
    //calculeaza a * b. rezultatul ==> a
    long long rez[N][N];
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
        {
            rez[i][j] = 0;
            for(int k = 0; k < N; k++)
                rez[i][j]=(rez[i][j]+a[i][k]*b[k][j]%MOD)%MOD;
        }
    }
    ///a <-- rez
    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
            a[i][j] = rez[i][j];
}

void power(long long a[N][N], long long n)
{
    ///a^n % MOD
     long long rez[N][N];
    ///initial rez = In
    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
            if(i == j)
                rez[i][j] = 1;
            else
                rez[i][j] = 0;
    while(n > 0)
    {
        if(n % 2 == 1)
            multiply(rez, a);

        multiply(a, a);
        n = n / 2;
    } ///a <-- rez
    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
            a[i][j] = rez[i][j];
}

int main()
{
    long long mt[N][N] = {{0,1},{1,1}};
    long long n;
    cin>>n;
    n=n-1;
    power(mt, n);
    ///calculam mat^n
    ///fib(0)=1, fib(1)=1
    ///(fib(0), fib(1)) * mat^n = (fib(n), fib(n+1))
    long long fibn = (mt[0][0] * 1 + mt[0][1] * 1) % MOD;
    cout << fibn;
    return 0;
}