Extra
Time
建筑师 Time:2s Memory:256M AC:0% Submit:0

★问题描述:
小Z是一个很有名的建筑师,有一天他接到了一个很奇怪的任务:在数轴上建n个建筑,
每个建筑的高度是1到n之间的一个整数。小Z有很严重的强迫症,他不喜欢有两个建筑的高
度相同。另外小Z觉得如果从最左边(所有建筑都在右边)看能看到A个建筑,从最右边(所
有建筑都在左边)看能看到B个建筑,这样的建筑群有着独特的美感。现在,小Z想知道满足
上述所有条件的建筑方案有多少种?
如果建筑i的左(右)边没有任何建造比它高,则建筑i可以从左(右)边看到。两种方案不
同,当且仅当存在某个建筑在两种方案下的高度不同。
★数据输入:
输入文件名为building.in。
第一行一个整数T,代表T 组数据。
接下来T行,每行三个整数n,A,B。
★结果输出:
输出文件名为building.out。
对于每组数据输出一行答案 mod (10 7) 9  。
★数据范围:
10% : 1 <= n <= 10
20% : 1 <= n <= 100
40% : 1 <= n <= 50000,1 <= T <= 5
100% :1 <= n <= 50000,1 <= A, B <= 100,1 <= T <= 200000。
输入示例
2
3 2 2
3 1 2

输出示例
2
1