Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 4076
Old Problem

Time Limit: 3 Seconds      Memory Limit: 65536 KB

Chiaki has an $n \times m$ grid map and there are $(n + 1) \times (m + 1)$ grid points on the map. She would like to know the number of grid right triangles whose area is $\frac{s}{2}$.

Input

There are multiple test cases. The first line of the input contains an integer $T$ ($1 \le T \le 10000$), indicating the number of test cases. For each test case:

The first line contains three integers $n$, $m$ and $s$ $(1 \le n, m, s \le 10^8)$.

Output

For each test case, output the answer modulo $(10^9+7)$.

Sample Input

2
1 1 1
2 2 2

Sample Output

4
24

Author: LIN, Xi
Source: Yet Another Xi Lin Contest
Submit    Status