Chanek 先生想要编织蜡染布,一种来自印度尼西亚的传统布料。布料形成一个网格$$$a$$$,尺寸为$$$n \times m$$$。有 $$$k$$$ 颜色,网格中的每个单元格都可以是 $$$k$$$ 颜色之一。
将子矩形定义为两个单元格 $$$((x_1, y_1), (x_2, y_2))$$$ 的有序对,表示 $$$a$$$ 中子矩形的左上角单元格和右下角单元格(包含)。当且仅当以下条件成立时,两个子矩形 $$$((x_1, y_1), (x_2, y_2))$$$ 和 $$$((x_3, y_3), (x_4, y_4))$$$ 具有相同的模式:
- 它们具有相同的宽度($$$x_2 - x_1 = x_4 - x_3$$$);
- 它们具有相同的高度($$$y_2 - y_1 = y_4 - y_3$$$);
- 对于每对 $$$(i, j)$$$,其中 $$$0 \leq i \leq x_2 - x_1$$$ 和 $$$0 \leq j \leq y_2 - y_1$$$,单元格的颜色 $$$(x_1 + i, y_1 + j)$$$ 和 $$$(x_3 + i, y_3 + j)$$$ 相等。
计算可能的蜡染颜色组合的数量,使得子矩形 $$$((a_x, a_y),(a_x + r - 1, a_y + c - 1))$$$ 和 $$$((b_x, b_y),(b_x + r - 1, b_y + c - 1))$$$ 具有相同的图案。
输出对 $$$10^9 + 7$$$ 取模的答案。
输入
第一行包含五个整数 $$$n$$$、$$$m$$$、$$$k$$$、$$$r$$$ 和 $$$c$$$ ($$$1 \leq n, m \leq 10^9$$$, $$$1 \leq k \leq 10^9$$$, $$$1 \leq r \leq \min(10^6, n)$$$, $$$1 \leq c \leq \min(10^6, m)$$$) — 蜡染的大小、颜色数量和子矩形的大小。
第二行包含四个整数 $$$a_x$$$、$$$a_y$$$、$$$b_x$$$ 和 $$$b_y$$$ ($$$1 \leq a_x, b_x \leq n$$$, $$$1 \leq a_y, b_y \leq m$$$) — 第一个和第二个的左上角子矩形。给出的两个子矩形都在网格内($$$1 \leq a_x + r - 1$$$、$$$b_x + r - 1 \leq n$$$、$$$1 \leq a_y + c - 1$$$、$$$b_y + c - 1 \leq m$$$)。
输出
输出一个整数,表示可能的蜡染颜色组合的数量,以 $$$10^9 + 7$$$ 为模。
示例
输入 #1
3 3 2 2 2 1 1 2 2
输出 #1
32
输入 #2
4 5 170845 2 2 1 4 3 1
输出 #2
756680455
注意
以下是第一个示例中所有 $$$32$$$ 可能的颜色组合。