abc

Time limit: 1s Memory limit: 256MB Input: Output:

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 AA, BB, and CC places in the three houses respectively, and the number of new students is A+B+CA + B + C, so there will be exactly AA new students in Andorgryff, BB in Bufflehuff, and CC 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 109+710^9 + 7. Two distributions are considered different if at least one student is assigned to a different house.

Input data

The first line contains TT, the number of test cases. Each of the following TT lines contains three integer numbers AA, BB and CC.

Output data

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

Constraints and Clarifications

  • 1T201 \le T \le 20;
  • 0A,B,C100 0000 \le A, B, C \le 100 \ 000;
  • A+B+C1A + B + C \ge 1;
  • The modulo operation (amodm)(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<109+7x < 10^9 + 7, then 2x2 x fits into a C/C++ int.
# Score Restrictions
1 0 Examples.
2 6 C=0C = 0.
3 9 A+B+C10A+B+C \le 10.
4 19 A,B,C100A, B, C \le 100.
5 23 A,B,C2 000A, B, C \le 2 \ 000.
6 14 C2C \le 2.
7 29 No additional limitations.

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.

Log in or sign up to be able to send submissions!