1926: 买鸡蛋2
内存限制：128 MB
时间限制：5.000 S
评测方式：文本比较
命题人：
提交：15
解决：4
题目描述
北化超市的鸡蛋降价了，现价0.5元一个，这一举动引起了很多同学的疯狂抢购，现在有m+n个同学都要买鸡蛋，其中m个同学只有一张0.5元的钱，另n个同学只有一张1元的钱，而卖鸡蛋的阿姨那里没有零钱。请问有多少种站队的方法能让说有人都能买上鸡蛋，人与人之间只有5毛和一块的区别，5毛和一块内部没有区别。
输入
输入一个数t表示t组数据(t < 100000)；接下来每行两个数据m和n（n ≤ m < 1000）。
输出
输出有多少种站队的方法。(结果模10000009)
样例输入 复制
3
1 1
2 2
18 18样例输出 复制
1
2
7638277