Veverita

#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("veverita.in");
ofstream fout("veverita.out");
const int MOD = 666013;
unsigned long long n;

int main()
{
    fin >> n;
    if(n <= 1000)
    {
        /// numere mari
        int R[1000];
        R[0] = 1;
        if(n % 2 == 0)
            R[1] = 2;
        else
            R[1] = 3;
        n /= 2;
        for(int i = 1 ; i <= n ; i ++)
        {
            int t = 0;
            for(int j = 1; j <= R[0] ; j ++)
            {
                int x = t + R[j] * 2;
                R[j] = x % 10;
                t = x / 10;
            }
            while(t)
                R[++R[0]] = t % 10, t /= 10;
        }
        for(int i = R[0] ; i > 0 ; i --)
            fout << R[i];

    }
    else
    {
        int F = (n % 2 == 0)?2:3;
        n /= 2;
        int A = 2, R = 1;
        while(n > 0)
        {
            if(n % 2 == 1)
                R = 1ULL * R * A % MOD;
            A = 1ULL * A * A % MOD;
            n /= 2;
        }
        fout << 1LL * F * R % MOD;
    }

    return 0;
}