324 : 塔の建造

$3 \times 3 \times n$の塔を$2 \times 1 \times 1$のブロックで埋める場合の数を$f(n)$とする。 ブロックは好きな方向に回転することができる。しかし、塔自身を回転・反転等させたものは別のものとして数える。

たとえば ($q=100\,000\,007$として)： $f(2) = 229,$ $f(4) = 117805,$ $f(10) \mod q = 96149360,$ $f(10^3) \mod q = 24806056,$ $f(10^6) \mod q = 30808124$

$f(10^{10000}) \mod 100000007$を求めよ。