AIRLINES  Jumbo Airlines
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
Multiple test cases, separated by blank lines.
Each test case consists of a single line containing three integers M, N and K. (M <= N)
There are two kinds of input:
The input of the first kind satisfies that 1<= M <=15, 1<= N <=50, 3<= K <=50.
The input of the second kind satisfies that 1<= M<= 4, 1<= N <= 10^{9}, 3<= K <=5.
Input terminates by EOF.
Output specification
For each test case output a single line with the number of allowed arrangements modulo 420047.
Example
Input: 2 4 4 Output: 2
Hint
The input file can be downloaded here. You may submit a TEXT file  the corresponding output file.
hide comments
abhays:
20190208 07:06:57
Why does this problem has #scc tag? 

siddharth9820:
20161226 18:44:06
Good practice for bitmasking. 
Added by:  Fudan University Problem Setters 
Date:  20090531 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  TEXT 
Resource:  IPSC 2009 