1554: 棋盘染色 -【蓝桥杯第十一届青少年组真题】
Memory Limit：128 MB
Time Limit：300.000 S
Judge Style：Text Compare
Creator：
Submit：4
Solved：3
Description
棋盘是一个n×m的矩形，分成n行m列共n*m个小方格。现在小蓝有c种不同颜色的颜料，他希望把棋盘用这些颜料染色，并满足以下规定：
1）每一个小方格可以染色，也可以不染色；
2）每一行至少有一个小方格被染色；
3）每一列至少有一个小方格被染色；
4）每种颜色在棋盘上至少出现一次。
请你求出满足要求的不同的染色方案总数。只要存在一个位置的颜色不同，即认为两个染色方案是不同的
Input
输入只有一行 3 个整数n,m,c。 1 < = n,m,c <=400 .
Output
输出一个整数，为不同染色方案总数。因为总数可能很大，只需输出总数mod 1,000,000,007的。
Sample Input Copy
2 2 3Sample Output Copy
60