Well, It's easy to see that at each step we will have 2ⁱ rows, also for each row the number of upwards triangles  = i.

So all we need is to know the number of rows, then the answer is under the mod of course.

I think most of the problems with only one input n, we need to observe a pattern, or equation, ..

Firstly, solve for small input data by brute force, logical ways, count on a paper, researching, etc. Try to understand what it is mean and get conclusion.

Secondly, solve it fast and compare with slow solution on small input data values.

This is my solution without reading tutorial. Let a(t) and b(t) — number of triangles "UP" and triangles "DOWN" in integer time t. From test in this problem we have:

a(0) = 1, b(0) = 0
a(1) = 3, b(1) = 1
a(2) = 10, b(2) = 6

Conclusion: on each iteration a(t+1) = 3 * a(t) + b(t), because all triangles "UP" from iteration t are duplicated 3 times, and all tiangles "DOWN" are duplicated 1 times and overturn, b(t+1) = a(t) + 3 * b(t) analogically. So, we have solution in O(n). How to speed up? Use matrixes — this is the way to speed up slow solution! We have formulas:

a(t+1) = 3 * a(t) + b(t)
b(t+1) = a(t) + 3 * b(t)

Let x(t) = {a(t), b(t)} — 2D vector, and A = {{3,1}, {1,3}} — 2D matrix. From formulas:

x(t+1) = A * x(t)
x(t+2) = A * A * x(t)
x(t+3) = A * A * A * x(t)

This is multiplication "matrix on matrix" and "matrix on vector". Finally formula for fixed integer time t:

x(t) = A^t * x(0)

Just use quick pow in O(log(n)) time and getting answer. Source.

Do not forget to compare the results with the slow algorithm on small numbers before sending.

UPD: accepted