#include <fstream>
#include <vector>

#define ll long long
#define P 666013

using namespace std;

ifstream cin ("kfib.in");
ofstream cout ("kfib.out");

struct matrix
{
    ll a,b,c,d;
};
matrix m;
ll n;
matrix multiplication (matrix x, matrix y)
{
    matrix res;
    res.a=(x.a*y.a)%P+(x.b*y.c)%P;
    res.b=(x.a*y.b)%P+(x.b*y.d)%P;
    res.c=(x.c*y.a)%P+(x.d*y.c)%P;
    res.d=(x.c*y.b)%P+(x.d*y.d)%P;
    return res;
}

matrix lg_power (matrix x, ll k)
{
    if (k==0) return {0,0,0,0};
    if (k==1) return {0,1,1,1};
    if (k==2) return {1,1,1,2};

    matrix res;
    if (k%2==0)
    {
        res=multiplication(lg_power(x,k/2),lg_power(x,k/2));
    }
    else
    {
        matrix y=multiplication(lg_power(x,k/2),lg_power(x,k/2));
        res=multiplication(y,x);
    }
    return res;
}

int main()
{
    cin>>n;
    m=lg_power({0,1,1,1},n);
    cout<<m.b%P<<"\n";
    return 0;
}