비밀번호 개수
시간 제한1초메모리 제한128 MB
숫자 키패드에서 인접한 버튼끼리만 연속으로 눌러 만들 수 있는 길이 N 비밀번호의 개수를 1,234,567로 나눈 나머지로 구합니다.
문제
석원이는 현관문에 숫자 버튼으로 된 비밀번호 기계를 설치했다. 버튼은 다음과 같이 놓여 있다.
1 2 3
4 5 6
7 8 9
0
두 버튼이 위아래 또는 양옆으로 맞닿아 있을 때 인접하다고 한다. 따라서 0은 7과만 인접한다.
길이가 N인 비밀번호는 위 버튼 중 하나를 차례로 눌러 만든다. 비밀번호에서 서로 이웃한 두 숫자는 기계에서도 반드시 인접해야 한다. 예를 들어 1과 5는 인접하지 않으므로 15는 만들 수 없지만, 1-2-3-6은 모든 이웃한 숫자 쌍이 인접하므로 만들 수 있다.
주희는 길이가 N인 비밀번호를 만들 수 있는 전체 경우의 수를 알고 싶다. 첫 숫자는 0도 될 수 있다.
입력
첫 번째 줄에 테스트 케이스의 수 T가 주어진다. 이어서 각 테스트 케이스마다 한 줄에 비밀번호의 길이 N이 주어진다.
1 <= N <= 1000
출력
각 테스트 케이스마다 조건을 만족하는 비밀번호의 개수를 한 줄에 하나씩 출력한다.
수가 매우 커질 수 있으므로, 답을 1,234,567로 나눈 나머지를 출력한다.