import java.util.Scanner;
public class Main {
public static void main(String[] arg) {
Scanner scanner = new Scanner(System.in);
// todo
}
}
NC205409. L2-3新旷野地带
描述
StarrySky 最近迷上了精灵宝可梦，在这款游戏中有一块区域称作旷野地带，在这片地带中分布有若干个极巨化坑，会有极巨化宝可梦在其中出没。
StarrySky 想要集齐图鉴，尤其是收集极巨化宝可梦，所以就需要常年来回奔波于各个极巨化坑之间。又由于这些极巨化坑的分布十分不规律，再加之总是出现雷雨、沙尘暴、暴风雪等天气降低能见度，StarrySky 总是在旷野地带迷路。
终于，StarrySky 忍受不了这个设定，决定破解这个游戏，自己重新设计一个旷野地带。
假设新旷野地带由 n 行 m 列组成，其中的每一个位置（如：i 行 j 列）都可以放置极巨化坑。现在 StarrySky 手中有 k 个极巨化坑有待放置，同时，为了不让极巨化坑的分布过于密集，他决定每一行、每一列最多同时放置一个极巨化坑，如：已经在 i 行 j 列放置了一个极巨化坑，那么，在第 i 行的其它位置不能再出现极巨化坑，同理，在第 j 列的其它位置也不能再出现极巨化坑。
k 个极巨化坑可以不全放入旷野地带，但是旷野地带中必须至少存在一个极巨化坑，StarrySky 现在想要知道一共有多少种放置方案，这个数量可能很大，所以请你给出答案对 1e9 + 7 取模后的结果。
StarrySky 想要集齐图鉴，尤其是收集极巨化宝可梦，所以就需要常年来回奔波于各个极巨化坑之间。又由于这些极巨化坑的分布十分不规律，再加之总是出现雷雨、沙尘暴、暴风雪等天气降低能见度，StarrySky 总是在旷野地带迷路。
终于，StarrySky 忍受不了这个设定，决定破解这个游戏，自己重新设计一个旷野地带。
假设新旷野地带由 n 行 m 列组成，其中的每一个位置（如：i 行 j 列）都可以放置极巨化坑。现在 StarrySky 手中有 k 个极巨化坑有待放置，同时，为了不让极巨化坑的分布过于密集，他决定每一行、每一列最多同时放置一个极巨化坑，如：已经在 i 行 j 列放置了一个极巨化坑，那么，在第 i 行的其它位置不能再出现极巨化坑，同理，在第 j 列的其它位置也不能再出现极巨化坑。
k 个极巨化坑可以不全放入旷野地带，但是旷野地带中必须至少存在一个极巨化坑，StarrySky 现在想要知道一共有多少种放置方案，这个数量可能很大，所以请你给出答案对 1e9 + 7 取模后的结果。
输入描述
一行三个由空格隔开的正整数 n, m, k，表示新旷野地带由 n 行 m 列组成，手中有 k 个可选择放置的极巨化坑。
输出描述
一行一个整数，表示满足题意的放置方案的数量对取模后的结果。
示例1
输入:
2 2 2
输出:
6
说明:
6 种放置方案如下：只在 (1, 1) 上放一个；
只在 (1, 2) 上放一个；
只在 (2, 1) 上放一个；
只在 (2, 2) 上放一个；
在 (1, 1), (2, 2) 上各放一个；
在 (1, 2), (2, 1) 上各放一个。