#include <bits/stdc++.h>
#define MOD 666013
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");

void afis(long long x[][5])
{
      for(int i=1;i<=x[1][0];++i)
    {
        for(int j=1;j<=x[0][1];++j)
                cout<<x[i][j]<<" ";
        cout<<'\n';
    }cout<<'\n';

}

void ori(long long b[][5], long long a[][5])
{
    long long c[5][5],s=0;

    for(int i=1;i<=b[1][0];++i)
    {
        for(int j=1;j<=a[0][1];++j)
        {
            s=0;
            for(int k=1;k<=b[0][1];++k)
                s=(s+b[i][k]*a[k][j]%MOD)%MOD;
            c[i][j]=s;
        }
    }

    for(int i=1;i<=b[1][0];++i)
        for(int j=1;j<=b[0][1];++j)
            b[i][j]=c[i][j];
}

void pwr(long long b[][5], long long p)
{
    if(p!=1)
    {
        if(p%2==0)
        {
            ori(b,b);
            pwr(b,p/2);
        }
        else
        {
            long long c[5][5];
            for(int i=0;i<=b[1][0];++i)
                for(int j=0;j<=b[0][1];++j)
                    c[i][j]=b[i][j];
            ori(b,b);
            pwr(b,p/2);
            ori(b,c);
        }
    }
}

long long n,b[5][5],a[5][5];
int main()
{
    fin>>n;

    b[0][1]=2;
    b[1][0]=2;

    b[1][1]=0;
    b[1][2]=b[2][1]=b[2][2]=1;

    pwr(b,n-1);

    a[1][0]=1;
    a[0][1]=2;
    a[1][1]=0;
    a[1][2]=1;

    ori(a,b);
    fout<<a[1][2];

    return 0;
}