超市的鸡蛋降价了，现价0.5元一个，这一举动引起了很多人的疯狂抢购，现在有2n个人都要买鸡蛋，其中n个人只有一张0.5元的钱，另n个人只有一张1元的钱，而售货员没有零钱。请问有多少种站队的方法能让所有人都能买上鸡蛋，人与人之间只有5毛和一块的区别，5毛和一块内部没有区别。

输入
输入一个数m表示m组数据(m < 10000)；接下来每行一个数据n(n < 10000)。

输出
输出有多少种站队的方法。(结果模10000009)

样例输入
3
1
2
18
样例输出
1
2
7638277
找规律好久没找到 实在纠结 求各路神仙赐教