2694: 【提高】棋盘染色
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
棋盘是一个n×m的矩形，分成n行m列共n*m个小方格。
现在小蓝有c种不同颜色的颜料，他希望把棋盘用这些颜料染色，并满足以下规定∶
1）每一个小方格可以染色，也可以不染色；
2）每一行至少有一个小方格被染色；
3）每一列至少有一个小方格被染色；
4）每种颜色在棋盘上至少出现一次。
请你求出满足要求的不同的染色方案总数。只要存在一个位置的颜色不同，即认为两个染色方案是不同的。
评分标准∶
30分 ∶ 完成题目样例和给出的一个样例；
50分 ∶ 在30分的基础上完成给出的另外一个样例；
100分∶在50分的基础上完成给出的最后一个样例。
现在小蓝有c种不同颜色的颜料，他希望把棋盘用这些颜料染色，并满足以下规定∶
1）每一个小方格可以染色，也可以不染色；
2）每一行至少有一个小方格被染色；
3）每一列至少有一个小方格被染色；
4）每种颜色在棋盘上至少出现一次。
请你求出满足要求的不同的染色方案总数。只要存在一个位置的颜色不同，即认为两个染色方案是不同的。
评分标准∶
30分 ∶ 完成题目样例和给出的一个样例；
50分 ∶ 在30分的基础上完成给出的另外一个样例；
100分∶在50分的基础上完成给出的最后一个样例。
输入
输入只有一行3个整数n，m，C。1<=n，m，C<=400.
输出
输出一个整数，为不同染色方案总数。因为总数可能很大，只需输出总数mod 1，000，000，007的值。
样例输入 复制
2 2 3样例输出 复制
60提示
11届国赛试题精选——C++