If you're using C++, you should use a class that allow you to use big numbers. I performed that making a bigNum struct, that store the number in a string. It has one function, that multiplies that value by a given integer. Then, return that value. Once you got that, make a function powBigNum, with parameters:

-a bigNum struct
-the exponent
-The number that you'll use as product.

this function returns a bigNum struct. So, you'll get in the main code something like that:

        if(n%3 == 0)
            cout << powBigNum(num, n/3, 3).n;
        else if(n%3 == 1)
            cout << powBigNum(num, (n/3)-1, 3).product(4);
        else if(n%3 == 2)
            cout << powBigNum(num, (n/3), 3).product(2);

My program got AC in 0.031 sec 368 KB. Hope you get AC too.