2×1×1 크기의 벽돌로 3×3×n 규모의 탑을 세우는 방법의 수를 f(n)으로 표기합니다.
벽돌을 어느 쪽으로 회전시켜 사용해도 됩니다만, 탑 전체가 회전되거나 반사된 경우는 모두 다른 것으로 계산합니다.

예를 들어 (여기서 q = 100000007입니다) :
f(2) = 229,
f(4) = 117805,
f(10) mod q = 96149360,
f(10³) mod q = 24806056,
f(10⁶) mod q = 30808124 입니다.

f(10¹⁰⁰⁰⁰) mod 100000007 값을 구하세요.