题目描述

萌萌有一个 $n$ 行 $m$ 列的花园，共 $n×m$ 个花坛。她手上有 $C$ 种不同的花种。现在她要为每个花坛选择是否种花，如果种，则从 $C$ 种花中选择一种。要求：

• 每一行至少有一个花坛种了花。
• 每一列至少有一个花坛种了花。
• 每一种花至少在花园中出现一次。

两个种植方案不同，当且仅当存在某个花坛，其种植的花种类不同（包括种与不种的区别）。 请你计算满足要求的种植方案总数，并对 $1000000007$ 取模。

输入格式

一行三个整数 $n,m,C$，分别表示行数、列数和花的种类数。

输出格式

输出一个整数，表示方案总数对 $1000000007$ 取模的结果。

样例

2 2 3

60

数据范围

对于 $20$% 的数据

• $1<=n,m<=3$
• $1<=c<=2$

对于 $100$% 的数据

• $1<=n,m,c<=400$