CF1575K.Knitting Batik

Mr. Chanek wants to knit a batik, a traditional cloth from Indonesia. The cloth forms a grid $a$ with size $n \times m$. There are $k$ colors, and each cell in the grid can be one of the $k$ colors.

Define a sub-rectangle as an ordered pair of two cells $((x_1, y_1), (x_2, y_2))$, denoting the top-left cell and bottom-right cell (inclusively) of a sub-rectangle in $a$. Two sub-rectangles $((x_1, y_1), (x_2, y_2))$ and $((x_3, y_3), (x_4, y_4))$ have the same pattern if and only if the following holds:

• they have the same width ($x_2 - x_1 = x_4 - x_3$);
• they have the same height ($y_2 - y_1 = y_4 - y_3$);
• for every pair $(i, j)$ where $0 \leq i \leq x_2 - x_1$ and $0 \leq j \leq y_2 - y_1$, the color of cells $(x_1 + i, y_1 + j)$ and $(x_3 + i, y_3 + j)$ are equal.

Count the number of possible batik color combinations, such that the subrectangles $((a_x, a_y),(a_x + r - 1, a_y + c - 1))$ and $((b_x, b_y),(b_x + r - 1, b_y + c - 1))$ have the same pattern.

Output the answer modulo $10^9 + 7$.

Chanek 先生想制作一块蜡染布，这是一种源自印度尼西亚的传统织物。该织物构成一个大小为 $n \times m$ 的网格 $a$。共有 $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$）；
• 对于所有满足 $0 \leq i \leq x_2 - x_1$ 且 $0 \leq j \leq y_2 - y_1$ 的数对 $(i, j)$，单元格 $(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$ 取模的结果。

The first line contains five integers $n$, $m$, $k$, $r$, and $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)$) — the size of the batik, the number of colors, and size of the sub-rectangle.

The second line contains four integers $a_x$, $a_y$, $b_x$, and $b_y$ ($1 \leq a_x, b_x \leq n$, $1 \leq a_y, b_y \leq m$) — the top-left corners of the first and second sub-rectangle. Both of the sub-rectangles given are inside the grid ($1 \leq a_x + r - 1$, $b_x + r - 1 \leq n$, $1 \leq a_y + c - 1$, $b_y + c - 1 \leq m$).

第一行包含五个整数 $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$）。

Output an integer denoting the number of possible batik color combinations modulo $10^9 + 7$.

输出一个整数，表示可能的蜡染颜色组合数对 $10^9 + 7$ 取模的结果。

The following are all $32$ possible color combinations in the first example.

以下是第一个示例中的全部 $32$ 种颜色组合。