[백준] 15988번 1, 2, 3 더하기 3

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner kb = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
        int T = kb.nextInt();
        int maxN = 1000000;
        long[] dy = new long[maxN+1];
        
        dy[1] = 1;
        dy[2] = 2;
        dy[3] = 4;
        
        for(int j=4; j<= maxN; j++) {
        	dy[j] = (dy[j-1]+ dy[j-2] + dy[j-3])%1000000009;
        }
        
        for(int i=0; i<T; i++) {
        	int n = kb.nextInt();
        	sb.append(dy[n]).append('\n');
        }

        
        System.out.print(sb.toString());

    }
}