타일 채우기
시간 제한1초메모리 제한128 MB
4×N 크기의 board를 2×1 도미노로 채우는 방법의 수를 여러 질의에 대해 계산하되 답이 32비트 정수 범위를 넘지 않도록 한다.
문제
높이가 4, 너비가 N인 직사각형 보드를 2×1 또는 1×2 크기의 도미노로 빈칸 없이 채우려고 한다. 도미노는 서로 겹치거나 보드 밖으로 나가면 안 된다.
N이 주어질 때, 보드를 채우는 서로 다른 방법의 수를 출력하시오.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 1 이상 1,000 이하이다. 이어지는 T개의 줄에는 각 테스트 케이스의 너비 N이 하나씩 주어진다. N은 자연수이다.
각 N은 정답이 2,147,483,647 이하가 되도록 주어진다.
출력
각 테스트 케이스마다 높이 4, 너비 N인 보드를 채우는 방법의 수를 한 줄에 하나씩 출력한다.