Number of ways to arrange the blocks should be

f(n)=2*f(n-1)+2*f(n-2); //We can fill just one col in two ways or two col in two ways.

But here we need to find: g(n)=f(n)f(0)+f(n-1)f(1)+....+f(0)f(n).

I can find f(n) using matrix expo but can't solve it for g(n).

Thanks for helping.

Since f(n) only depends on the previous two values f(n-1) and f(n-2), the sequence eventually begins to repeat itself — in this case after only a relatively small number of steps which you can work out using a simple loop.

With that in mind, you can take a loop like this which runs in O(N):

...And since the i-th iteration is the same as the (i % repeat)th iteration, turn it into a loop like this which runs in O(repeat):

Thanks. I got AC using matrix expo.