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>
#include <bits/stdc++.h>
using namespace std;
struct rect {
  long long ax, ay, bx, by;
};
long long c;
const long long MOD = 1e9 + 7;
long long binpow(long long a, long long n) {
  if (n == 0) return 1;
  if (n % 2 == 0) {
    long long g = binpow(a, n / 2);
    return (g * g % MOD);
  } else {
    return (binpow(a, n - 1) * a % MOD);
  }
}
rect merge(rect a, rect b) {
  long long r = min(a.bx, b.bx), l = max(a.ax, b.ax);
  if (l > r) return {-1, -1, -1, -1};
  long long rr = min(a.by, b.by), ll = max(a.ay, b.ay);
  if (ll > rr) return {-1, -1, -1, -1};
  return {l, ll, r, rr};
}
long long func(rect a, rect b) {
  rect c = merge(a, b);
  long long val = (a.bx - a.ax + 1) * (a.by - a.ay + 1);
  if (a.ax == b.ax && a.ay == b.ay && a.bx == b.bx && a.by == b.by) {
    return val;
  }
  if (c.ax == -1) {
    return val;
  }
  rect d = c;
  long long r = c.ax - a.ax, q = c.ay - a.ay;
  d.ax -= r, d.bx -= r, d.ay -= q, d.by -= q;
  long long mem = func(c, d);
  return val - 2 * (c.bx - c.ax + 1) * (c.by - c.ay + 1) + mem;
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  long long n, m, k, r, ans = 0;
  long long ax, ay, bx, by;
  cin >> n >> m >> k >> r >> c >> ax >> ay >> bx >> by;
  rect a{ax, ay, ax + r - 1, ay + c - 1}, b{bx, by, bx + r - 1, by + c - 1};
  ans = n * m - (r * c) * 2;
  rect ccc = merge(a, b);
  if (ccc.ax != -1) {
    ans += (ccc.bx - ccc.ax + 1) * (ccc.by - ccc.ay + 1);
  }
  ans += func(a, b);
  cout << binpow(k, ans) << endl;
  return 0;
}
