Robust Forest Connections

In this problem, you are given a forest with N trees and M existing connections. Your task is to select exactly k connections to form a robust forest structure. Although the underlying combinatorial process might be complex in a real-world scenario, here the solution is simplified. You only need to compute the result as $$k \mod 10^9+7$$, where $$10^9+7$$ (written in LaTeX format) is the modulus.

inputFormat

The input is given via standard input (stdin). The first line contains an integer T, representing the number of test cases. Each of the next T lines contains three integers: N, M, and k, where:

• N represents the number of trees.
• M represents the number of existing connections.
• k is the required number of connections.

outputFormat

For each test case, output a single integer on a new line – the number of ways computed as $$k \mod 10^9+7$$. The output should be sent to standard output (stdout).## sample

1
3 2 3

3