0%

Problem 324


Problem 324


Building a tower

Let f(n) represent the number of ways one can fill a 3×3×n tower with blocks of 2×1×1.
You’re allowed to rotate the blocks in any way you like; however, rotations, reflections etc of the tower itself are counted as distinct.

For example (with q = 100000007) :
f(2) = 229,
f(4) = 117805,
f(10) mod q = 96149360,
f(103) mod q = 24806056,
f(106) mod q = 30808124.

Find f(1010000) mod 100000007.


建塔

记f(n)是用2×1×1的砖块建造一座3×3×n的塔的方式数。
你可以随意地旋转方块;然而将塔进行旋转或翻转则视为不同的建造方式。

举例而言(其中q = 100000007):
f(2) = 229,
f(4) = 117805,
f(10) mod q = 96149360,
f(103) mod q = 24806056,
f(106) mod q = 30808124。

求f(1010000) mod 100000007。