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;
const int mod = 1000000007;
long long mpow(long long a, long long b) {
  long long ans = 1;
  while (b) {
    if (b & 1) ans = ans * a % mod;
    b >>= 1;
    a = a * a % mod;
  }
  return ans;
}
pair<int, int> get_intersect(int x1, int y1, int x2, int y2, int r, int c) {
  if (x1 == x2 && y1 == y2) return make_pair(r, c);
  int x3 = x1 + r - 1, y3 = y1 + c - 1;
  int x4 = x2 + r - 1, y4 = y2 + c - 1;
  int lx = 0, ly = 0;
  if (x1 <= x2 && x2 <= x3) lx = x3 - x2 + 1;
  if (y1 <= y2 && y2 <= y3)
    ly = y3 - y2 + 1;
  else if (y2 <= y1 && y1 <= y4)
    ly = y4 - y1 + 1;
  return make_pair(lx, ly);
}
long long get_free(int r, int c, int first, int second) {
  long long ans = 1LL * r * c;
  for (int i = 1; i <= first; i++)
    for (int j = 1; j <= second; j++) {
      for (int k = 1;; k++)
        if (i + 1LL * k * first <= r && j + 1LL * k * second <= c)
          ans--;
        else
          break;
    }
  return ans;
}
int main() {
  long long n, m, k, r, c;
  cin >> n >> m >> k >> r >> c;
  long long tot = n * m - 2 * r * c;
  int x1, y1, x2, y2;
  cin >> x1 >> y1 >> x2 >> y2;
  if (x1 > x2)
    swap(x1, x2);
  else if (x1 == x2 && y1 > y2)
    swap(y1, y2);
  pair<int, int> inter = get_intersect(x1, y1, x2, y2, r, c);
  tot += 1LL * inter.first * inter.second;
  if (1LL * inter.first * inter.second == 0) {
    cout << mpow(k, tot) * mpow(k, 1LL * r * c) % mod << endl;
    return 0;
  }
  long long ans =
      mpow(k, tot) * mpow(k, get_free(r, c, inter.first, inter.second)) % mod;
  cout << ans << endl;
  return 0;
}
