Old Problem

题号：NC21532
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

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

输入描述:

There are multiple test cases. The first line of the input contains an integer T (1 ≤ T ≤ 10000), indicating the number of test cases. For each test case:
The first line contains three integers n, m and s (1 ≤ n, m, s ≤ 10⁸).

输出描述:

For each test case, output the answer modulo (10⁹+7).

示例1

输入

复制

2
1 1 1
2 2 2

输出

复制

4
24