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

import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        int t=Integer.parseInt(br.readLine());
        long[] num=new long[1000001];
        num[1]=1;
        num[2]=2;
        num[3]=4;
        for(int i=4; i<num.length; i++){
            num[i]=(num[i-1]+num[i-2]+num[i-3])%1000000009;
        }
        for(int i=0; i<t; i++){
            int temp=Integer.parseInt(br.readLine());
            bw.write(num[temp]+"\n");
        }
        bw.flush();



    }
}