BOJ 2780 비밀번호

문제 링크:

문제 내용

다음과 같이 생긴 키패드가 있습니다.

123
456
789
0

하나의 숫자를 선택한 다음에는 그 숫자와 상하좌우로 인접한 숫자만 선택할 수 있다고 할 때, $N$개의 숫자를 순서대로 선택하는 방법의 수를 $1\;234\;567$로 나눈 나머지를 출력하세요.

입력

첫 번째 줄에는 테스트 케이스의 개수 $T$가 주어집니다. ($1 \le T \le 1000$)

각 테스트 케이스에 대해 $N$의 값이 주어집니다. ($1 \le N \le 1000$)

출력

각 테스트 케이스에 대해, 문제의 정답을 한 줄에 출력합니다.

문제 풀이