3656: icebound的商店--2018HBCPC J

icebound在得到神殿的宝藏之后，开了一家神秘的商店。KK来到了商店，发现慷慨的icebound搞了T次促销活动。在每次促销活动中，icebound都会想出一个他喜欢的数字，如果你买的商品的总价刚好等于icebound喜欢的数字，那么你就可以免费得到这些商品。icebound的商店里一共有 15 件商品，商品的价格和这家商店一样神秘，第一件商品的价格是 1 元，第二件商品的价格是 2 元，设第n件商品的价格为w_n元，则w_n=w_n-1+w_n-2(3<=n<=15)。

如果在某次活动中icebound喜欢的数字是 4，那么共有 4 种购买方案：

买 4个 第一种商品，
买 2个 第一种商品 和 1个 第二种商品，
买 2个 第二种商品，
买 1个 第一种商品 和 1个 第三种商品

请你算出共有多少种方案可以免费购物，方案数对1000000009(=10^9+9)取模。

第一行给出一个整数T，表示icebound搞了T次活动。 接下来的T行每行给出一个正整数x，表示在这次活动中icebound喜欢的数字。 1<=T<=3000,1<=x<=3000.

输出T行，每行输出一个正数。 第i行的正数表示在第i次活动中免费购物的方案数，方案数对1000000009(10^9+9)取模。

3
5
20
30

6
134
509