Unique String

Replay of Comilla Univers...
Limits 1s, 512 MB

There are 3 types of letters available. They are A, B and C. You are given the frequencies of them. You have to make a word with all of them but have to maintain one condition that letter A and B will not be adjacent to each other. How many different words you can make maintaining the condition.

For example, if the frequencies of letter A, B and C are 1, 1 and 2, the answer will be 6. The words are ACCB, ACBC, CACB, BCAC, BCCA and CBCA.

Input

First line of input contains the number of test cases T (1<= T <= 100000). Next T lines describe the case. Each case contains three integers x, y and z where x denotes the frequency of A, y denotes the frequency of B and z denotes the frequency of C (0 <= x, y, z <= 100000 && min(x, y) < 3 && (x + y + z) ≥ 1).

Output

For each test case, output a single line contains “Case X: Y” without any quote where X denotes the number of test cases and Y denotes the answer of the problem. Answer could be very large so output the answer modulo 1000000007.

Sample

InputOutput
2
1 1 1
1 1 2
Case 1: 2
Case 2: 6

Submit

Login to submit.

Statistics

10% Solution Ratio
ovis96Earliest, Dec '17
ovis96Fastest, 253292.1s
ovis96Lightest, 18 MB
ovis96Shortest, 1816B
Toph uses cookies. By continuing you agree to our Cookie Policy.