FORMAT1 - Counting Formations

With the coming release of Marcohard Balconies 100 operating system, people are more and more interested in its new UI (User Interface), code-named “Subway”.

This UI presents your desktop as a grid that is divided into N rows and M columns (so you have N * M cells). In each cell, you can place one icon of an application of a certain type. Your applications can be of one of K types, numbered 1 through K. You’re an expert in this field, so it is assumed that there is an unlimited number of applications of each type.

Any placement is called an icon formation. Some of the icon formations are beautiful. An icon formation is called beautiful if and only if no pair of rows are similar. Two rows are similar if and only if for each X that 1 <= X <= K, they contain exactly the same number of applications of type X.

Given N, M, and K, you should solve for the number of different icon formations that are beautiful, modulo 109+7. Two formations are different if and only if there is a cell where the type of application in one formation is not the same as the type in another formation.

You may assume that 1 <= N, M, K <= 50.

Input

There are several test cases. For each test case there are 3 integers, named N, M, K, in a single line. Please process until EOF (End Of File).

Output

For each test case, please print a single line with a integer, the corresponding answer to this case.

Example

Input:
2 2 2
5 3 2
3 5 7

Output:
10
0
894953467

Added by:Fudan University Problem Setters
Date:2012-02-12
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Not my own problem, used in ICPC Regional Contest, Chengdu 2012 Preliminary

hide comments
2023-07-27 16:48:32 Oleg
Another hint: There are no many "hard" tests cases. my AC solution calculates "50 50 50" for 0.7s.
2020-05-10 01:26:24 Ashish Lavania
This problem mustered all the combinatorics I had in me. Nice problem!
2018-10-17 00:56:01 :D
Very good problem.

As a hint: O(X^5) precalc, where X = max(N, M, K) passes (I obfuscated complexity with X as to not reveal to much of the solution). My time is significantly worse than that for best solutions, so maybe this can be reduced a little. I doubt that O(X^4) was used however. Maybe other solvers will comment.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.