#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops", \
                     "omit-frame-pointer", "inline")
#pragma GCC target( \
    "sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,fma,tune=native")
#pragma GCC option("arch=native", "no-zero-upper")
using namespace std;
const long long mod = (1e9 + 7);
const double eps = (1e-9);
const long long oo = (long long)(1e18 + 5);
long long k;
long long qp(long long b, long long e) {
  long long ans = 1;
  while (e) {
    if (e & 1) ans = (ans * b) % mod;
    e >>= 1;
    b = (b * b) % mod;
  }
  return ans;
}
long long solve(long long dx, long long dy, long long r, long long c) {
  if (dx == 0 && dy == 0) return qp(k, r * c);
  if (dx >= r || dy >= c) return qp(k, r * c);
  long long nr = r - dx;
  long long nc = c - dy;
  long long mul;
  if (2 * nr - r >= 0 && 2 * nc - c >= 0)
    mul = qp(k, 2 * dx * dy);
  else
    mul = qp(k, r * c - 2 * nr * nc);
  return (mul * solve(dx, dy, nr, nc)) % mod;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  long long n, m, r, c;
  cin >> n >> m >> k >> r >> c;
  long long ax, ay, bx, by;
  cin >> ax >> ay >> bx >> by;
  if (ax > bx) {
    ax = n - (ax + r - 1);
    bx = n - (bx + r - 1);
  }
  if (ay > by) {
    ay = m - (ay + c - 1);
    by = m - (by + c - 1);
  }
  long long cx = ax + r - bx;
  long long cy = ay + c - by;
  cx = max(cx, 0ll);
  cy = max(cy, 0ll);
  long long ans = qp(k, n * m - 2 * r * c + cx * cy);
  ans = (ans * solve(bx - ax, by - ay, r, c)) % mod;
  cout << (ans) << '\n';
  return 0;
}

### Prompt

In CPP, your task is to solve the following problem:

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>
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops", \
                     "omit-frame-pointer", "inline")
#pragma GCC target( \
    "sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,fma,tune=native")
#pragma GCC option("arch=native", "no-zero-upper")
using namespace std;
const long long mod = (1e9 + 7);
const double eps = (1e-9);
const long long oo = (long long)(1e18 + 5);
long long k;
long long qp(long long b, long long e) {
  long long ans = 1;
  while (e) {
    if (e & 1) ans = (ans * b) % mod;
    e >>= 1;
    b = (b * b) % mod;
  }
  return ans;
}
long long solve(long long dx, long long dy, long long r, long long c) {
  if (dx == 0 && dy == 0) return qp(k, r * c);
  if (dx >= r || dy >= c) return qp(k, r * c);
  long long nr = r - dx;
  long long nc = c - dy;
  long long mul;
  if (2 * nr - r >= 0 && 2 * nc - c >= 0)
    mul = qp(k, 2 * dx * dy);
  else
    mul = qp(k, r * c - 2 * nr * nc);
  return (mul * solve(dx, dy, nr, nc)) % mod;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  long long n, m, r, c;
  cin >> n >> m >> k >> r >> c;
  long long ax, ay, bx, by;
  cin >> ax >> ay >> bx >> by;
  if (ax > bx) {
    ax = n - (ax + r - 1);
    bx = n - (bx + r - 1);
  }
  if (ay > by) {
    ay = m - (ay + c - 1);
    by = m - (by + c - 1);
  }
  long long cx = ax + r - bx;
  long long cy = ay + c - by;
  cx = max(cx, 0ll);
  cy = max(cy, 0ll);
  long long ans = qp(k, n * m - 2 * r * c + cx * cy);
  ans = (ans * solve(bx - ax, by - ay, r, c)) % mod;
  cout << (ans) << '\n';
  return 0;
}

```