Killjee loves playing with numbers. Recently, his friend, Sam, gave him 3 numbers N, M, and R and asked him to find a magic value of these numbers.

The magic value of three numbers = \(\Big( \sum_{i=1}^{R-1} {N \choose i} * {M \choose (R-i)} * i * (R-i) \Big) \% (10^7+19)\).

INPUT FORMAT

The first line of input contains a single integer T denoting the number of test cases. T line follows each containing 3 space separated integers N, M, and R.

OUTPUT FORMAT

For each test case, print the magic value in new line.

INPUT CONSTRAINTS

• \(1 \le N,M \le 10^{18}\)
• \( R \le (N+M)\)
• \(1 \le T \le 100\)