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`

# | Score | Restrictions |
---|---|---|

1 | 0 | Examples. |

2 | 6 | $C = 0$. |

3 | 9 | $A+B+C \le 10$. |

4 | 19 | $A, B, C \le 100$. |

5 | 23 | $A, B, C \le 2 \ 000$. |

6 | 14 | $C \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.