方格填数
Description
小 Z 正在研究方格！现在在小 Z 面前有个 n × m 的方格图，其中每个方格上都有一个 
的正整数。
小 Z 对于最大值很感兴趣，因此，她会留意这个方格图中的"极大方格"。对于某个方格，他是极大方格当且仅当这个方格中的数字严格大于与该方格同行或是同列的其他方格的数字。
现在这个方格图所有方格都是空的，定义 f(i) 为使方格图的"极大方格"数不少于 i 的填数方案。小 Z 想要知道，
的值？
由于这个结果可能很大，小 Z 只要求你求出答案对于109 + 7取模的结果即可。
输入一行共三个整数 n, m, k (1 ≤ n, m ≤ 106, 1 ≤ k ≤ 1018)，含义如上文所述。
输出一行共一个整数，表示答案的值对109 + 7取模的结果。
Input
输入一行共三个整数 n, m, k (1 ≤ n, m ≤ 106, 1 ≤ k ≤ 1018)，含义如上文所述。
Output
输出一行共一个整数，表示答案的值对109 + 7取模的结果。
1 2 3
11 45 14
114514 1919 810
15
181394144
710129823
Note
对于第一个样例，一共有 {1, 1}、{1, 2}、{1, 3}、{2, 1}、{2, 2}、{2, 3}、{3, 1}、{3, 2}、{3, 3} 共 9 种填数方案，其中"极大方格"数分别为 0、1、1、1、0、1、1、1、0。f(0) = 9，f(1) = 6，其余 f(x) 值均为 0，因此答案为 15。