Clash Of Kingdoms
All submissions for this problem are available.
You are the master strategist of your kingdom. Your neighbouring kingdom has started a war with your kingdom, and you have to plan the formation of your soldiers in order to beat him.
The war arena consists of N rows and M columns which consists of N * M cells. You should place exactly one soldier in each cell in the arena.
There are K types of soldiers in your army and you have infinite supply of each type of soldiers. Being a strategist you have found
out that if your formation of soldiers in the arena have a weak pair, you will lose the battle.
A formation is said to have a weak pair, if any pair of rows for each X between 1 and K inclusive contain the same number of soldiers of type X.
Your task is to find out the number of formations possible so that you don't lose the battle (Meaning you don't have any weak pair in your formation).
- Each test case contains three space seperated integers N, M, K denoting the number of rows, number of columns and the number of type of soldiers respectively.
- Output a single line containing the total number of formations possible so that you don't lose the battle. As the answer may be large, Output the answer MOD 109 + 7
- 1 ≤ N ≤ 10
- 1 ≤ M ≤ 50
- 1 ≤ K ≤ 100
Example - 1
Input: 2 1 3 Output: 6
Example - 2
Input: 1 2 3 Output: 9
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.