#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
inline int add(int x, int y) {
  int ret = x + y;
  if (ret >= mod) ret -= mod;
  return ret;
}
inline int sub(int x, int y) {
  int ret = x - y;
  if (ret < 0) ret += mod;
  return ret;
}
inline int mul(int x, int y) { return ((long long)x * y) % mod; }
inline int step(int base, int pw) {
  int ret = 1;
  while (pw) {
    if (pw & 1) ret = mul(ret, base);
    base = mul(base, base);
    pw >>= 1;
  }
  return ret;
}
inline int invv(int x) { return step(x, mod - 2); }
const int maxn = 1e5 + 10;
int m, n, k, r, c, ax, ay, bx, by;
struct rect {
  int x1, x2, y1, y2;
  long long surface() {
    if (x1 > x2 || y1 > y2) return 0;
    return ((long long)x2 - x1 + 1) * (y2 - y1 + 1);
  }
};
rect intersect(rect &a, rect &b) {
  rect ret;
  ret.x1 = max(a.x1, b.x1);
  ret.x2 = min(a.x2, b.x2);
  ret.y1 = max(a.y1, b.y1);
  ret.y2 = min(a.y2, b.y2);
  return ret;
}
int go(rect a, rect b) {
  if (intersect(a, b).surface() == 0ll) return step(k, a.surface() % (mod - 1));
  if (a.surface() == intersect(a, b).surface())
    return step(k, a.surface() % (mod - 1));
  rect pom = intersect(a, b);
  rect pom2 = pom;
  int dx = a.x1 - b.x1;
  int dy = a.y1 - b.y1;
  pom2.x1 += dx;
  pom2.y1 += dy;
  pom2.x2 += dx;
  pom2.y2 += dy;
  int ret = step(k, (a.surface() - pom.surface() - pom2.surface() +
                     intersect(pom, pom2).surface()) %
                        (mod - 1));
  ret = mul(ret, go(pom, pom2));
  return ret;
}
int main() {
  scanf("%d %d %d %d %d", &n, &m, &k, &r, &c);
  scanf("%d %d %d %d", &ax, &ay, &bx, &by);
  rect a = {ax, ax + r - 1, ay, ay + c - 1};
  rect b = {bx, bx + r - 1, by, by + c - 1};
  int rez = step(k, ((long long)n * m -
                     (a.surface() + b.surface() - intersect(a, b).surface())) %
                        (mod - 1));
  rez = mul(rez, go(a, b));
  printf("%d\n", rez);
  return 0;
}

### Prompt

Develop a solution in cpp to the problem described below:

Mr. Chanek wants to knit a batik, a traditional cloth from Indonesia. The cloth forms a grid a with size n × 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 ≤ i ≤ x_2 - x_1 and 0 ≤ j ≤ 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.

Input

The first line contains five integers n, m, k, r, and c (1 ≤ n, m ≤ 10^9, 1 ≤ k ≤ 10^9, 1 ≤ r ≤ min(10^6, n), 1 ≤ c ≤ 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 ≤ a_x, b_x ≤ n, 1 ≤ a_y, b_y ≤ m) — the top-left corners of the first and second sub-rectangle. Both of the sub-rectangles given are inside the grid (1 ≤ a_x + r - 1, b_x + r - 1 ≤ n, 1 ≤ a_y + c - 1, b_y + c - 1 ≤ m).

Output

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

Examples

Input


3 3 2 2 2
1 1 2 2


Output


32


Input


4 5 170845 2 2
1 4 3 1


Output


756680455

Note

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

<image>

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
inline int add(int x, int y) {
  int ret = x + y;
  if (ret >= mod) ret -= mod;
  return ret;
}
inline int sub(int x, int y) {
  int ret = x - y;
  if (ret < 0) ret += mod;
  return ret;
}
inline int mul(int x, int y) { return ((long long)x * y) % mod; }
inline int step(int base, int pw) {
  int ret = 1;
  while (pw) {
    if (pw & 1) ret = mul(ret, base);
    base = mul(base, base);
    pw >>= 1;
  }
  return ret;
}
inline int invv(int x) { return step(x, mod - 2); }
const int maxn = 1e5 + 10;
int m, n, k, r, c, ax, ay, bx, by;
struct rect {
  int x1, x2, y1, y2;
  long long surface() {
    if (x1 > x2 || y1 > y2) return 0;
    return ((long long)x2 - x1 + 1) * (y2 - y1 + 1);
  }
};
rect intersect(rect &a, rect &b) {
  rect ret;
  ret.x1 = max(a.x1, b.x1);
  ret.x2 = min(a.x2, b.x2);
  ret.y1 = max(a.y1, b.y1);
  ret.y2 = min(a.y2, b.y2);
  return ret;
}
int go(rect a, rect b) {
  if (intersect(a, b).surface() == 0ll) return step(k, a.surface() % (mod - 1));
  if (a.surface() == intersect(a, b).surface())
    return step(k, a.surface() % (mod - 1));
  rect pom = intersect(a, b);
  rect pom2 = pom;
  int dx = a.x1 - b.x1;
  int dy = a.y1 - b.y1;
  pom2.x1 += dx;
  pom2.y1 += dy;
  pom2.x2 += dx;
  pom2.y2 += dy;
  int ret = step(k, (a.surface() - pom.surface() - pom2.surface() +
                     intersect(pom, pom2).surface()) %
                        (mod - 1));
  ret = mul(ret, go(pom, pom2));
  return ret;
}
int main() {
  scanf("%d %d %d %d %d", &n, &m, &k, &r, &c);
  scanf("%d %d %d %d", &ax, &ay, &bx, &by);
  rect a = {ax, ax + r - 1, ay, ay + c - 1};
  rect b = {bx, bx + r - 1, by, by + c - 1};
  int rez = step(k, ((long long)n * m -
                     (a.surface() + b.surface() - intersect(a, b).surface())) %
                        (mod - 1));
  rez = mul(rez, go(a, b));
  printf("%d\n", rez);
  return 0;
}

```