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。