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

5
7 1 3
4 2 3
8 1 2
10 1 5
3 3 4

2642
10233
264
12589025
487936

5
5 1 4
7 1 2
2 4 5
2 4 5
5 2 2

1514
135
744625
744625
1184