Gauss

Time Limit: 1000 ms

Memory Limit: 65535 ms

Description

1+2+3+...+n-1+n=(n+1)*n/2;Guass was the first to discover this equation. Now your task is to give the result of the following formula.a*(a+1)*(a+2)*..(a+k)+(a+1)*(a+2)*..(a+k)*(a+k+1)+...+n*(n+1)*(n+2)*..(n+k-1)*(n+k)

Input

The first line contains an integer t ( 1 <= t <= 10 ): the number of test cases. Then for each test case:The first line contains three integers a,k,n ( 0 < a <= 1000 , 0 <= k <= 1000 ,a < n <=10^8).

Output

For each test case, output the result in the form of sample.You should print the case number and the answer mod 100000007.

Sample Input

2
1 0 100
2 4 10

Sample Output

Case 1: 5050
Case 2: 600480

Hint

None

Source

陶翔专场练习赛

提交代码