광성이는 꿈에 그리던 집을 가지게 되었습니다. 평소 살고 싶었던 자연에 동화된 집으로 창밖에는 바다가 보이고, 뒷면에는 산이 있어서 시간이 나면 산에도 언제든 올라갈 수 있습니다.

그런데 이 집엔 한가지 단점이 있었는데, 전에 살던 사람이 난장판으로 화장실을 사용했는지 화장실 타일 일부가 깨져 있었습니다. 깔끔한 광성이는 이 모습을 보기 싫어서 근처 인테리어 물품 판매점에 타일을 사려고 찾아가보니 구입할 수 있는 타일이 안타깝게도 한 종류 밖에 없었습니다. 인터넷 배송으로 더 좋은걸 살까도 싶었지만 당장 화장실을 바꾸고 싶어서 그 자리에서 타일을 충분한 양을 구매 했습니다.

구입한 타일은 가로 길이 2, 세로 길이 1인 타일로 산뜻한 민무늬에 평소 좋아하던 초록색을 띄고 있습니다.

깨진 부위를 뜯어내고 나니 높이는 2이고 너비는 N인 횡한 벽이 드러났습니다. 타일이 정방형이 아니여서 붙이는 방법에 따라 여러가지 모양이 나올 수 있음을 안 광성이는 갑자기 한가지 궁금한점이 생겼습니다.

가지고 있는 타일로 벽을 채울때 몇가지의 방법으로 채울 수 있을까요?

호기심은 왕성하지만 도무지 이걸 어떻게 계산해야 할지 모르는 광성이를 위해 너비 N이 주어졌을 때 벽면을 채울 수 있는 방법의 수를 알려주는 프로그램을 작성 해 주세요.

테스트 케이스의 수 T (1 <= T <= 10) 가 주어지며, 

그 다음줄 부터 벽면의 너비 N (1 <= N <= 100)이 T개 주어집니다.

한줄에 하나씩 가능한 가지수를 출력 해 주세요. 단, 너무 큰 숫자가 나올 수 있으니 결과값을 1,000,000,007 로 나눈 나머지를 출력해주세요.