Python's pow() is made for this.

I'm not sure why you're adding one to your power and multiplying by two. Ignore the outside lines, and it's easy to see that we have 0 lines at n=0, 2 at n=1, 4 at n=2, etc. Further, we can visualise that each new row and each new column will be split at each second, so if we have m lines at n=t, then we will have m+2m lines at n=t+1 (all lines are length 1 of course), written in summation form, we can see that:

4 + {∑(i=1,n) 2^i} will yield the answer (we'll have to check the 0 case later), so let's look at that summation.

I claim that ∑(i=1,n) 2^i = 2^(n+1) - 2

Base case, n=1: 2^(1+1) - 2 = 4-2 = 2 = 2^1

Inductive case: Hypothesis ∑(i=1,k) 2^k = 2^(k+1) - 2 and we need to show that ∑(i=1,k+1) 2^k = 2^(k+2) - 2

∑(i=1,k+1) 2^k = {∑(i=1,k) 2^k} + 2^(k+1) by definition, which, by our hypothosis is (2^(k+1) - 2) + 2^(k+1)

To make this next part a little clearer, let 2^(k+1) be u

So u - 2 + u = 2u - 2 replacing back in gives 2 * 2^(k+1) - 2 which we can write as 2^1 * 2^(k+1) - 2 and properties of exponents tells us that this is the same as 2^(k+1+1)-2 or 2^(k+2) -2.

As for the problem, we still have those initial 4 lines, but it's easy to see that 4 + 2^(n+1) - 2 = 2^(n+1) + 2. Also, for n = 0, 2^(0+1) + 2 gives us 4 as expected, though we didn't cover that in our proof.

The only other issue is efficiently calculating the power. We know that (a*b)%m = (a%m * b%m)%m, and as numbers get extremely large, this greatly reduces the computational power necessary to multiply.

num can be as large as 10**9, think about taking power of a number in a fast way..