Description

开会，是对所有人时间的浪费，是对集体的谋杀。

苟利国家生死以，岂因祸福避趋之。

小G为了备战高考，沉迷于诗歌鉴赏。我们可以将一首诗作看做一个\(n\)行\(m\)列的矩阵，每个字看做一个\([1,k]\)范围内的整数。现在小G随机生成一首诗作，即诗 作中的每个字都是\([1,k]\)范围内随机生成的整数。诗作中的一个字为炼字当且仅当该字所在行的其他字都比他小且该字所在列的其他字都比他小。对于一首随机生成的诗作，定义诗作的精彩度为诗作中炼字的个数。定义\(f_i\)为精彩度为\(i\)的诗作的方案数目，显然，\( \sum_{i=0}^{nm} f_i=nm \)。现需要你求出\( \sum_{i=0}^{nm} i \times f_i \;mod \;( 10^9 +7) \)。

Format

Input

一行三个整数\(n, m, k\)。

Output

一行一个整数表示答案。

Sample 1

Input

2 2 2

Output

8

Limitation

1s, 512MiB for each test case.

Hint

样例解释

f0 = 10, f1 = 4, f2 = 2, f3 = f4 = 0。

数据规模与约定

对于所有数据， \(2 ≤ n, m ≤ 10^9, 1 ≤ k ≤ 10^6\)。

测试点编号	\(n, m\)	\(k\)
1～12	\(≤4\)	\(≤5\)
13～16	\(≤10^2\)	\(≤10^2\)
17～20	\(≤10^9\)	\(≤10^6\)

Source

CSP2019模拟试题五