====== 2×n 타일링 ======

===== 풀이 =====
  * 기초적인 DP문제. 그래서 변형 문제도 많다.
    * 2x2 타일을 추가하면 [[ps:problems:boj:11727]] 이 된다.
    * 여기에서 채워야 하는 칸을 3xn으로 바꾸면 [[ps:problems:boj:2133]] 이 된다.
    * 이 문제 자체는 프로그래머즈의 [[ps:problems:programmers:12900]]과 동일한 문제이다
  * 2xn을 채우는 방법은 두가지로 나뉜다
    * 2x(n-1)을 채우고, 마지막에 2x1 타일을 붙이는 방법
    * 2x(n-2)을 채우고, 마지막에 1x2 타일 두개를 붙이는 방법
  * 따라서 점화식은 dp[n] = dp[n-2] + dp[n-1]처럼 되고, 이것은 [[ps:피보나치 수]]의 점화식이므로, 답도 피보나치 수열이 된다.
  * n+1번째 [[ps:피보나치 수]]를 구하면 되므로 시간복잡도는 O(logn).

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 11726. 2×n 타일링".

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

Tags: [Fibonacci]
"""

from teflib import combinatorics

MOD = 10007


def main():
    n = int(input())
    print(combinatorics.fibonacci(n + 1, MOD))


if __name__ == '__main__':
    main()
</dkpr>
  * Dependency: [[:ps:teflib:combinatorics#fibonacci|teflib.combinatorics.fibonacci]]

{{tag>BOJ ps:problems:boj:실버_3}}