• 타일 채우기 문제에서 n의 범위만 증가시킨 문제.
  • 타일 채우기는 O(n)으로 풀어도 통과 가능하게 되어 있고, 이 문제는 O(logn)으로 풀어야만 통과 가능하게 되어 있다.

• 타일 채우기 참고. 동일하다.

"""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()

• Dependency: teflib.combinatorics.linear_homogeneous_recurrence