[アルゴリズム/標準]15988:1,2,3プラス3(python)



1 2 3 4 5
1 2 4 7 13
dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
a = list(int(input())for _ in range(int(input())))
dp = [0, 1, 2, 4] + [0] * max(a)

for i in range(4, max(a)+1):
    dp[i] = (dp[i-1]+dp[i-2]+dp[i-3]) % 1000000009
for i in a:
    print(dp[i])