폴리매스

원형파이는 벽을 예쁜 타일 장식으로 꾸미려고 한다.

벽은 2*N 크기이다.

원형파이는 흰색 타일로만 벽을 꾸미길 바라는데, 갖고 있는 흰색 타일들에는 2*2짜리 타일과 1*2짜리 타일이 있다.

1*2짜리 타일들은 세로로 돌려서 2*1짜리 타일로 이용해도 된다.

또한 원형파이는 타일이 떨어지면 마법을 이용해 생성할 수 있다.

하지만 이 마법은 다른 크기의 타일을 만들 수는 없다. 무조건 2*2 아니면 1*2짜리를 생성할 수 있다.

N이 주어지면, 벽을 꾸밀 수 있는 가짓수를 10억7로 나눈 수를 구하여라.

(1) N = 1

(2) N = 2

(3) N = 100

(4) N = 100000

(5) N = 100000000