Killjee and Sum
Problem
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 = (∑R−1i=1(Ni)∗(M(R−i))∗i∗(R−i))%(107+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≤N,M≤1018
- R≤(N+M)
- 1≤T≤100
Time Limit: 4
Memory Limit: 256
Source Limit:
Explanation
For first test case magic value = (3 choose 1) * (2 choose 1) * (1) * (1), which is eqaul to 6.
