Coco is running a chocolate factory. Chocolates from this factory are rectangles of width and height . Coco wants to divide the chocolate into domino pieces ( or ) and sell them. Somehow is always odd, so Coco decided to take away a piece of his liking, and divide the rest.
Given and the position of the piece, calculate the number of ways Coco can divide the rest of the chocolate into domino pieces.
The first line of input contains , the number of test cases. ()
For each test case, the integers , , and are given on one line, separated by spaces. and indicate that the piece chosen is at row and column . (, , )
For each test case, output the answer modulo on its own line.
is odd in all test cases.