Cực đại địa phương

Điểm: 1800 (thành phần)

Thời gian: 3.0s

Bộ nhớ: 256M

Input: bàn phím

Output: màn hình

Tác giả:

Sunlight

Dạng bài

Cho một bảng $n$ hàng, $m$ cột. Người ta xét tất cả khả năng điền các số từ $1$ đến $k$ vào bảng. Một ô trong bảng được gọi là cực đại địa phương nếu như nó thoả mãn số được điền lớn hơn tất cả các ô cùng hàng và cùng cột. Hãy đưa ra giá trị $\displaystyle \sum_{g \, = \, 0}^{n \, \cdot \, m} (g + 1) \cdot A(g)$ trong đó $A(g)$ là số cách điền bảng sao cho có chính xác $g$ ô cực đại địa phương.

Input

Dòng đầu tiên chứa số nguyên $T$ ( $1 \le T \le 5$ ) là số lượng test.
Trong $T$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $n$ , $m$ và $k$ ( $1 \leq n, m \leq 10^{10^6}$ , $1 \leq k \leq 10^6$ ) lần lượt là số hàng, số cột của bảng và giá trị tối đa được điền.

Output

Gồm $T$ dòng, dòng thứ $i$ in ra phần dư trong phép chia đáp án của test thứ $i$ cho $10 ^ 9 + 7$ .

Scoring

Subtask 1 ( $10\%$ số điểm): $n \cdot m \le 10$ , $k \le 5$ .
Subtask 2 ( $20\%$ số điểm): $n, m \le 2000$ , $k = 2$ .
Subtask 3 ( $30\%$ số điểm): $n, m, k \le 200$ .
Subtask 4 ( $30\%$ số điểm): $n, m \le 10^6$ .
Subtask 5 ( $10\%$ số điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input

Output

Note

Trong test thứ nhất: $A(0) = 1732$ , $A(1) = 455$ , $A(2) = 0$ , $A(3) = 0$ , $A(4) = 0$ , $A(5) = 0$ , $A(6) = 0$ và $A(7) = 0$ nên $\displaystyle \sum_{g \, = \, 0}^{7} (g + 1) \cdot A(g) = 2642$ .
Trong test thứ hai: $A(0) = 3765$ , $A(1) = 1920$ , $A(2) = 876$ , $A(3) = 0$ , $A(4) = 0$ , $A(5) = 0$ , $A(6) = 0$ , $A(7) = 0$ và $A(8) = 0$ nên $\displaystyle \sum_{g \, = \, 0}^{8} (g + 1) \cdot A(g) = 10233$ .

Test 2

Input

Output

Bình luận

Không có bình luận nào.