Migrated from Lutece 1187 Convex Polygon

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Cute qzy wants to calculate how many convex polygons with M vertices and K acute angles when selecting M vertices in a regular polygon with N vertices(N is odd).But he is busy with girls,so he asks you for help.Can you solve it?

Input

The first line contains a number T, indicating the number of test cases.(T≤50000)

For each case, there are three numbers N(3≤N≤100000), M(3≤M≤N), K(0≤K≤M), as described previously.

Output

For each case, print the Case #d: answer mod 1000000007 in each line.

Samples

1
5 4 2

Case #1: 5

Note

Resources

Prepare for 2015 MU2015 Multi-University Training