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⁹, 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.