Mirror IIOT 2022-2023, International Round | abc

In the Berlandian school of witchcraft and wizardry, Wartshog, each year newcomer students are distributed between three houses: Andorgryff, Bufflehuff, and Clawenrave. The distribution is done by a hat, called the Distributing Hat. The students put on the hat one by one (in a certain fixed order), and the hat shouts out loud the name of the house to which the student will belong. This year, there are $A$, $B$, and $C$ places in the three houses respectively, and the number of new students is $A + B + C$, so there will be exactly $A$ new students in Andorgryff, $B$ in Bufflehuff, and $C$ in Clawenrave. The Distributing Hat follows one additional rule: no two consecutive students will be put in the same house.

Can you tell how many different ways exist for distributing the students between the houses? Since this number might be very big, you need to give the answer modulo $10^9 + 7$. Two distributions are considered different if at least one student is assigned to a different house.

Input data

The first line contains $T$, the number of test cases. Each of the following $T$ lines contains three integer numbers $A$, $B$ and $C$.

Output data

For each test case, output a single number on a separate line, the number of different ways to distribute the students, modulo $10^9 + 7$.

Constraints and Clarifications

• $1 \le T \le 20$;
• $0 \le A, B, C \le 100 \ 000$;
• $A + B + C \ge 1$;
• The modulo operation $(a \bmod m)$ can be written in C/C++/Python as (a % m). To avoid the integer overflow error, remember to reduce all partial results through the modulus, and not just the final result!
• Notice that if $x < 10^9 + 7$, then $2 x$ fits into a C/C++ int.

Example

stdin

5
2 3 0
2 2 1
4 1 1
100 100 100
100000 100000 1

stdout

1
12
0
105481704
600000

Explanation

In the first sample case, there is only one possible distribution: BABAB (here we write the initial letter of the chosen house for each student in order).

In the second sample case, the 12 possible ways are: ABABC, ABACB, ABCAB, ABCBA, ACBAB, BABAC, BABCA, BACAB, BACBA, BCABA, CABAB, CBABA.

In the third sample case, there will be at least two consecutive A-s in any distribution, so the hat has no way to distribute the students.