Convex Polygon

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 272 Accepted Submission(s): 63

Problem 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.

Sample Input

1
5 4 2

Sample Output

Case #1: 5

Hint

Author

UESTC

Source

2015 Multi-University Training Contest 7

Statistic | Submit | Discuss | Note

Home | Top

Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-06-29 15:57:11, Gzip enabled

Administration