====== 타일 채우기 2 ======
  * [[ps:problems:boj:2133|타일 채우기]] 문제에서 n의 범위만 증가시킨 문제.
    * [[ps:problems:boj:2133|타일 채우기]]는 O(n)으로 풀어도 통과 가능하게 되어 있고, 이 문제는 O(logn)으로 풀어야만 통과 가능하게 되어 있다.

===== 풀이 =====
  * [[ps:problems:boj:2133|타일 채우기]] 참고. 동일하다.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 13976. 타일 채우기 2".

- Problem link: https://www.acmicpc.net/problem/13976
- Solution link: http://www.teferi.net/ps/problems/boj/13976
"""

from teflib import combinatorics

MOD = 1_000_000_007


def main():
    n = int(input())
    print(0 if n % 2
          else combinatorics.linear_homogeneous_recurrence([4, -1], [1, 3],
                                                           n // 2, MOD))


if __name__ == '__main__':
    main()
</dkpr>

  * Dependency: [[:ps:teflib:combinatorics#linear_homogeneous_recurrence|teflib.combinatorics.linear_homogeneous_recurrence]]

{{tag>BOJ ps:problems:BOJ:골드_1}}