Mancunian has recently learnt about trees in graph theory.
A tree is an undirected connected graph having no cycles.
The degree of a vertex is defined as the number of nodes it is connected to, in the tree.
In this problem, we consider only trees having at least 2 nodes and whose vertices have degree at most 3.
Given three integers A, B and C, can you help Mancunian count the number of labeled trees having exactly A vertices of degree 1, B vertices of degree 2 and C vertices of degree 3? As the answer can be very large, output the answer modulo 1000000009.
Two trees are said to be equivalent iff they have exactly the same set of undirected edges.

Input:
The first line contains a single integer T specifying the number of test cases.
Each of the next T lines contain three integers A, B and C.

Output:
For each test case, output a single integer in a new line which is the answer to the problem.

Constraints:
1 <= T <= 200
0 <= A, B, C <= 200
A+B+C >= 2