Find Arrangements

Schedule exactly P physics classes and C chemistry classes so that the same subject never appears more than N times in a row; find the number of distinct subject sequences modulo 1000000007. Each line is an independent test, and classes of the same subject have no individual identities.

输入格式

The first line contains T, followed by T lines of P C N. Full source ranges: 1≤T≤100, 1≤P,C,N≤1000.

输出格式

Output T integers in input order, one result per line, each modulo 1000000007.

样例 1

输入：

1
1 1 2

输出：

2

样例 2

输入：

1
1 2 1

输出：

1

样例 3

输入：

2
3 1 1
2 2 1

输出：

0
2

样例说明

The example outputs are 2, 1; and 0 2 respectively.