The new catchphrase of Jumbo Airlines is “No annoying neighbors, each flight a unique experience!”
And as in most cases, the advertisement was produced by the marketing department, without ever consulting the engineers. They only learned about it after the boss asked them to “handle it ASAP”.
There are M seats in each row, and there are N rows of seats in the airplane. Hence the seats form an M ×N grid. (For the purpose of this problem we will ignore the presence of aisles.) The airline sells exactly K tickets for each flight.
To make sure that the “no annoying neighbors” part of the motto is satisfied, the seating must obey the following rule: Whenever a seat is occupied, the seats immediately in front of it and behind it, as well as the seats immediately to the left and to the right must remain free.
An allowed arrangement is a set of K occupied seats that obeys the rule above.
The “unique experience” part of the motto is then satisfied by using a different arrangement of occupied seats for each flight. (Two seating arrangements are different if there is at least one seat which is occupied in one arrangement and free in the other.)
Problem specification
You are given the numbers M, N and K. Find the number of different allowed seating arrangements.
As this number can be very large, we’re only interested in its value modulo 420047.
Input specification
The first line of the input file contains an integer T specifying the number of test cases. Each test case is preceded by a blank line.
Each test case consists of a single line containing three integers M, N and K.
Output specification
For each test case output a single line with the number of allowed arrangements modulo 420047.
Example
| input
3
2 3 2 2 4 4 2 5 1 |
| output
8
2 10 |