#include <cstdio>
#define MOD 666013
#define NMAX 100000

using namespace std;

int a[5][5],p[5][5];
int n;

int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    scanf("%d",&n);
    a[1][1]=0;a[1][2]=1;
    a[2][1]=1;a[2][2]=1;
    p[1][1]=1;p[2][2]=1;
    int b = n;
    while(b > 0)
    {
        if(b % 2 == 1)
        {
            // p = p * a
            int rez[3][3] = {0};
            for(int i = 1; i <= 2; ++i)
                for(int j = 1; j <= 2; ++j)
                    for(int k = 1; k <= 2; ++k)
                    {
                        rez[i][j] = ( (1ll * p[i][k] * a[k][j])%MOD + rez[i][j]) % MOD;
                    }
            for(int i = 1; i <= 2; i++)
                for(int j = 1; j <= 2; j++)
                    p[i][j] = rez[i][j];
            b = b-1;
        }
        else
        {
            //a = a * a
           int rez[3][3] = {0};
            for(int i = 1; i <= 2; ++i)
                for(int j = 1; j <= 2; ++j)
                    for(int k = 1; k <= 2; ++k)
                    {
                        rez[i][j] = ( (1ll * a[i][k] * a[k][j])%MOD + rez[i][j]) % MOD;
                    }
            for(int i = 1; i <= 2; i++)
                for(int j = 1; j <= 2; j++)
                    a[i][j] = rez[i][j];
            b = b / 2;
        }
    }

    printf("%d\n", p[1][2] % MOD);
    return 0;
}