As we all know Assi has fractured his hand while showing off his unique talent of skateboarding. Even though according to Assi he is an expert in skateboarding. (really ??) but somehow he was able to achieve that feat( fracturing his hand). So, he decided to celebrate that feat with his friends. Like Assi his party is also unique. All the dishes will be prepared with Aaloo and Pyaaz only. So he went to market.

In market, shopkeeper gave him A packets of aaloo and B packets of pyaaz, Now he is wondering no of ways he can put those packets in K bags where some bags can be empty also.

Input

The first line of the input contains a single integer T (1 ≤ T≤ 100000) — the number of test cases.

Each test case contains 3 integers A, B and K ( 1 <= A,B,K <= 100000 )

Output

A single integer ( no of ways ) modulo 1000000007.