染色问题

• 时间限制：1 秒
• 内存限制：256 MiB

题目描述

有一个 $n\times m$ 的矩形棋盘，共有 $c$ 种互不相同的颜色。每个格子可以不染色，也可以染成这 $c$ 种颜色中的一种。

一种合法方案必须同时满足：

1. 每一行至少有一个格子被染色；
2. 每一列至少有一个格子被染色；
3. 每一种颜色都至少出现一次。

只要至少一个格子的状态不同（包括是否染色或所染颜色不同），就认为两种方案不同。求合法染色方案数。

输入格式

输入一行三个整数 $n,m,c$。

输出格式

输出一个整数，表示合法方案数对 $1\,000\,000\,007$ 取模的结果。

样例输入

2 2 3

样例输出

60

数据范围

保证 $1\le n,m,c\le400$。