老虎和蒜头是好朋友。

老虎最近学习了矩阵的相关知识。出于好奇，老虎想要计算值域为 $ c $ 的 $ n \times m $ 的矩阵数目对 $ 10^9 +7 $ 取模的值。

对于两个矩阵 $ A $ 和 $ B $ 来说，若我们能够只通过有限次将某个矩阵的两行或两列交换的操作，从 $ A $ 矩阵得到 $ B $ 矩阵，我们称这两个矩阵是相同的。

你能帮老虎解决这个问题吗？

输入格式

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

输出格式

输出共一行，包括一个整数，表示答案。

样例一

input

2 3 2

output

13

数据范围

对于 100% 的数据，$ 1 \le c \le 10^9 $ 。

Subtask 1(17 分): $ 1 \le n \times m \le 10, c = 2 $

Subtask 2(15 分): $ 1 \le n, m \le 4, c = 2 $

Subtask 3(21 分): $ 1 \le n, m \le 6 $

Subtask 4(18 分): $ 1 \le n, m \le 9 $

Subtask 5(18 分): $ 1 \le n, m \le 20 $

Subtask 6(11 分): $ 1 \le n, m \le 44 $

时间限制: 3s

空间限制: 512MB