题目描述

给定$n\times m$的棋盘，以及$k$种颜色，棋盘中所有格子初始没有颜色，现在对这些格子进行染色，要求：

1.格子可以染色，可以不染。 2.每一行至少有一个格子被染色。 3.每一列至少有一个格子被染色。 4.每种颜色在棋盘上都至少出现一次。

请求出满足要求的染色方案数。

输入格式

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

输出格式

输出一行一个整数，表示你的答案。答案在模$10^9+7$意义下。

样例输入 #1

2 2 3

样例输出 #1

60

说明/提示

有$1\leq n,m,k\leq 400$。