[BOJ] 15990. 1, 2, 3 더하기 5

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		long[][] dp = new long [100001][4];
		dp[1][1] = 1l;
		dp[1][2] = 0l;
		dp[1][3] = 0l;
		dp[2][1] = 0l;
		dp[2][2] = 1l;
		dp[2][3] = 0l;
		dp[3][1] = 1l;
		dp[3][2] = 1l;
		dp[3][3] = 1l;
		for(int i = 4; i <= 100000; i++) {
			dp[i][1] = (dp[i-1][2]%1000000009 + dp[i-1][3]%1000000009)%1000000009;
			dp[i][2] = (dp[i-2][1]%1000000009 + dp[i-2][3]%1000000009)%1000000009;
			dp[i][3] = (dp[i-3][1]%1000000009 + dp[i-3][2]%1000000009)%1000000009;
		}
		
		int N = sc.nextInt();
		for(int i = 0; i < N; i++) {
			int M = sc.nextInt();
			long answer = (dp[M][1]%1000000009 + dp[M][2]%1000000009 + dp[M][3]%1000000009)%1000000009; 
			System.out.println(answer);
		}
		sc.close();
	}
}