Project Euler Problem 324
Let f(n) represent the number of ways one can fill a 3 times 3 times n tower with blocks of 2 times 1 times 1.
Solution
Answer: 96972774
A standard way to solve this problem is to model the tilings layer-by-layer with a transfer matrix on the $2^9=512$ boundary states of a $3\times3$ slice.
Let a state encode which cells of the next layer are already occupied by dominoes protruding upward from the current layer.
For every pair of boundary masks $(a,b)$, compute the number of ways to complete one layer so that the incoming mask is $a$ and the outgoing mask is $b$. This produces a $512\times512$ transfer matrix $T$.
Then:
$$f(n)=(T^n)_{0,0}.$$
The matrix is highly sparse, and only 252 states are reachable from the empty state. After compression, fast matrix exponentiation modulo
$$q=100000007$$
gives:
$$f(10)\equiv 96149360 \pmod q,$$
$$f(10^3)\equiv 24806056 \pmod q,$$
$$f(10^6)\equiv 30808124 \pmod q,$$
matching the values in the problem statement.
Finally, exponentiating to height
$$10^{10000}$$
yields:
Answer: 96972774