1924: 买鸡蛋
内存限制：128 MB
时间限制：5.000 S
评测方式：文本比较
命题人：
提交：88
解决：28
题目描述
北化超市的鸡蛋降价了，现价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