Holly Bee lives at location in a 3D Cartesian space and wants to go to Infinity, a tea shop franchise where each shop is located at some . To get there, she must perform a series of moves in the following forms:
- Walk. This only applies when Holly is on the ground (i.e., when ). If Holly is at , then she can go to either or in one move.
- Fly. If Holly is at , then she can go to as long as , , and .
Note that Holly Bee must be on a lattice point after each move.
Holly Bee has Infinity shops near her meadow. She knows that there are many paths she can take to reach each Infinity shop, but she wants to know the exact number of paths she can take to each shop. Given the 3D coordinates for Infinity shops, find and print the number of ways for Holly Bee to get to each shop on a new line. Recall that Holly Bee always starts at location .
Input Format
The first line contains an integer, , denoting the number of Infinity shops.
Each line of the subsequent lines describes the location of an Infinity tea shop in the form of three space-separated integers denoting the respective , , and values of the shop's location.
Constraints
For of the maximum score:
For the remaining the maximum score:
Output Format
For each Infinity tea shop location , print the number of different paths from to using some sequence of walk and fly moves described above. As this number can be very large, your answer must be modulo .
Sample Input
4
3 1 4
1 4 3
2 2 2
11 24 69
Sample Output
3
4
6
909000199
Explanation
There are Infinity tea shops near Holly Bee's meadow. For the purposes of this explanation, represents walk and represents fly.
For the first tea shop, there are three different paths to location :
Thus, we print on a new line as our first line of output. Note that something like would not be a valid sequence of moves because the fly movement does not satisfy the condition that .
For the third tea shop, there are six different paths to location :
Thus, we print on a new line as our third line of output.