무릎 문제 (어려움)

어두운 던전을 헤맨다. 주변에는 모양과 색이 다른 문들이 있다. 그중 하나를 골라 열고 안으로 들어간다.

"네가 올 줄 알았다." 어둠 속에서 목소리가 들린다. 가까이 다가가니 긴 흰 수염을 기른 노인이 바닥에 앉아 있다.

"나도 예전에는 너처럼 문제를 푸는 사람이었어. 그런데 무릎에 화살을 맞았지."

"정말요?" 하고 묻는다.

"글쎄, 사실은 아니야. 내가 마지막으로 햇빛을 봤을 때 아이들이 하던 말이 그것뿐이었지."

"그럼 무슨 일이 있었던 거예요?" 하고 물으며 노인 옆에 앉는다.

"사실 계단에서 무릎뼈를 망가뜨렸어. 젊을 때는 프로그래밍 대회에 많이 나갔지. 그중 한 대회에서 아주 까다로운 문제가 나왔어. n단으로 된 계단을 오르내리는 방법의 수를 구해야 했지. 제약도 있었어. 올라갈 때는 한 번에 두 칸씩, 내려갈 때는 한 번에 최대 네 칸까지 갈 수 있다고 했어."

노인은 깊게 한숨을 쉰다. "그 문제를 어떻게 풀어야 할지 전혀 몰랐어. 그래서 계단을 찾아가 가능한 경우를 전부 시도해 보기로 했지. 그런데 경우가 너무 많아서 무릎에 무리가 갔고, 지금은 걷지도 못해. 그래서 여기 앉아서 아직도 풀이를 생각하고 있어. 이 문제를 드디어 끝낼 수 있게 도와줄 수 있겠니?"

계단은 n단으로 이루어져 있다. 다음 제약 아래에서 계단을 올라갔다가 다시 내려오는 방법의 수를 구하라.

• 올라갈 때는 한 번에 1단 또는 2단씩 갈 수 있다.
• 내려갈 때는 한 번에 1단, 2단, 3단, 또는 4단씩 갈 수 있다.

경우의 수가 매우 클 수 있으므로, $10^9 + 9$로 나눈 나머지를 구하라.

계단은 n단으로 이루어져 있다. 다음 제약 아래에서 계단을 올라갔다가 다시 내려오는 모든 방법의 수를 구하라.

• 올라갈 때는 한 번에 1단 또는 2단씩 갈 수 있다.
• 내려갈 때는 한 번에 1단, 2단, 3단, 또는 4단씩 갈 수 있다.
• 내려갈 때는 올라갈 때 사용한 단 위로만 걸을 수 있다.

다시 한번, 유효한 경로의 수를 $10^9 + 9$로 나눈 나머지로 구하라.

위 그림에서 빨간 경로는 이 하위 문제에서 유효하지 않다. 내려갈 때 올라갈 때 쓰지 않은 4단을 밟기 때문이다. 파란 경로(0 → 2 → 4 → 5 → 2 → 0)는 유효하다.

입력의 첫 줄에는 테스트 케이스의 개수 t가 주어진다. 각 테스트 케이스 앞에는 빈 줄이 있다.

각 테스트 케이스는 한 줄로 이루어지며, 정수 n (1 ≤ n ≤ 100,000)이 주어진다. n은 계단의 단 수다.

각 테스트 케이스마다 유효한 경로의 수를 $10^9 + 9$로 나눈 나머지를 한 줄에 출력한다.