Đầu năm học, mỗi lớp sinh viên phải bầu ra một ban cán sự. Xét một lớp có ~n~ sinh viên nam và ~m~ sinh viên nữ (các sinh viên là những người khác nhau). Lớp cần chọn ra ban cán sự gồm đúng ~k~ sinh viên; các thành viên trong ban có vai trò như nhau, vì vậy một cách chọn chỉ được xác định bởi tập hợp ~k~ sinh viên được chọn. Theo quy định của nhà trường, ban cán sự phải có ít nhất một sinh viên nữ.

Hai cách chọn được coi là khác nhau nếu có một sinh viên thuộc ban cán sự ở cách này nhưng không thuộc ban cán sự ở cách kia.

Phòng Công tác sinh viên cần đếm số cách chọn ban cán sự cho ~q~ lớp, mỗi lớp có bộ ba ~(n, m, k)~ riêng.

Yêu cầu

Với mỗi lớp, hãy đếm số cách chọn ban cán sự thoả mãn quy định. Vì kết quả có thể rất lớn, chỉ cần đưa ra phần dư của nó khi chia cho ~10^9 + 7~.

Dữ liệu vào

• Dòng thứ nhất chứa số nguyên dương ~q~ – số lớp cần xét;
• ~q~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~n~, ~m~, ~k~ mô tả một lớp.

Kết quả ra

Ghi ra ~q~ dòng, dòng thứ ~i~ chứa một số nguyên là số cách chọn ban cán sự của lớp thứ ~i~ sau khi lấy phần dư cho ~10^9 + 7~.

Ràng buộc

~1 \le q \le 10^5~; ~0 \le n \le 5 \cdot 10^5~; ~1 \le m \le 5 \cdot 10^5~; ~1 \le k \le n + m~.

• Subtask 1 (20% số điểm – test 01–04): ~n + m \le 20~ và ~q \le 100~;
• Subtask 2 (30% số điểm – test 05–10): ~n + m \le 2000~;
• Subtask 3 (50% số điểm – test 11–20): không có ràng buộc bổ sung.

Ví dụ

Dữ liệu vào mẫu 1

4
2 2 2
0 3 2
3 1 4
10 5 3

Kết quả ra mẫu 1

5
3
1
335

Giải thích

Lớp thứ nhất có ~2~ nam, ~2~ nữ: có ~6~ cách chọn ~2~ người trong ~4~ người, trong đó đúng ~1~ cách chọn cả hai nam, nên còn ~5~ cách hợp lệ. Lớp thứ hai không có nam nên cả ~3~ cách chọn ~2~ trong ~3~ nữ đều hợp lệ. Lớp thứ ba phải chọn cả ~4~ người: ~1~ cách. Lớp thứ tư: có ~455~ cách chọn ~3~ người trong ~15~ người, trừ đi ~120~ cách chọn toàn nam, còn ~335~ cách.