#include <fstream>

using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
const int Mod = 666013;
long long a[3][3] = {{0,0,0},{0,0,1},{0,1,1}};
long long p[3][3] = {{0,0,0},{0,1,0},{0,0,1}};
void lgput(int b)
{
    while(b)
    {
        long long aux[3][3]={{0,0,0},{0,0,0},{0,0,0}};
        if(b%2==0)
        {
            b/=2;
            for(int i=1;i<=2;i++)
            {
                for(int j=1;j<=2;j++)
                {
                    for(int k=1;k<=2;k++)
                    {
                        aux[i][j]+=(a[i][k]*a[k][j])%Mod;
                        aux[i][j]%=Mod;
                    }
                }
            }
            for(int i=1;i<=2;i++)
            {
                for(int j=1;j<=2;j++)
                {
                    a[i][j]=aux[i][j];
                }
            }
        }
        else
        {
            --b;
            for(int i=1;i<=2;i++)
            {
                for(int j=1;j<=2;j++)
                {
                    for(int k=1;k<=2;k++)
                    {
                        aux[i][j]+=(1LL*p[i][k]*a[k][j])%Mod;
                        aux[i][j]%=Mod;
                    }
                }
            }
            for(int i=1;i<=2;i++)
            {
                for(int j=1;j<=2;j++)
                {
                    p[i][j]=aux[i][j];
                }
            }
        }
    }
}
int main()
{
    int n;
    f>>n;
    if(n<2)
    {
        g<<n<<'\n';
        return 0;
    }
    lgput(n);
    g<<p[2][1]<<'\n';
    return 0;
}