문제2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.아래 그림은 2×17 직사각형을 채운 한가지 예이다.입력첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)출력첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 예제 입력8예제 출력171 문제 링크풀이2 x 1인 타일을 기준으로 최대 n개부터 0개를 사용할 때 경우의 수를 계산했다. 1 x 2 타일은 반드시 2개를 사용하여 2 x 2로 만들어 사용이 가능하다.따라서, 2 x 2와 1 x 2는 하나로 통일해서 처리한 후 (2^사용 개수)로 경우의 수를 구할 수 있다. 1. y는 가로길이이며, 2 x 1 타일을 사용한 후 남은 길이가 짝수여야 2 x 2 타일..