Surya is always fascinated by the pascal ka triangle. He loves its symmetry, he loves the fact that value at any index is the sum of upper two indices and he loves everything else about. One day he decided to start with values a and b (ab twist to aayegha hi na story me) at the top instead of 1 and 1 and continued creating the triangle by taking sum of upper indices. He wants to find the sum of values at the nth row of the triangle but he can't create the triangle for large values of n (insan hi he yr). Help him find the answer. As the answer can be very large, print it's modulo 10^9+7.

Input
first line contain T (test cases)
Each test case of consist of single line contains three integers a, b ,n. (0 < a,b,n <10^9)

Output
Print a single integer representing the sum of values at nth row of the triangle modulo 10^9+7.For each test case output in new line.