#include <bits/stdc++.h>
using namespace std;
int n, m, k, res;
const int mo = 1000000007;
pair<int, int> a, b, c, d;
int ksm(int x, long long y) {
  int ans = 1;
  while (y) {
    if (y & 1) ans = 1ll * ans * x % mo;
    x = 1ll * x * x % mo;
    y = y / 2;
  }
  return ans;
}
int main() {
  res = 1;
  scanf("%d%d%d%d%d", &n, &m, &k, &c.first, &c.second);
  scanf("%d%d%d%d", &a.first, &a.second, &b.first, &b.second);
  if (a > b) swap(a, b);
  int doit = 1;
  while (doit) {
    if (a == b) {
      res = 1ll * res * ksm(k, 1ll * n * m);
      break;
    }
    d = make_pair(0, 0);
    if (a.first + c.first - 1 >= b.first) {
      if (a.second <= b.second && a.second + c.second - 1 >= b.second) {
        d = make_pair(a.first + c.first - b.first,
                      a.second + c.second - b.second);
      } else if (a.second >= b.second && b.second + c.second - 1 >= a.second) {
        d = make_pair(a.first + c.first - b.first,
                      b.second + c.second - a.second);
        b.second = a.second;
        a.second = a.second + c.second - d.second;
      }
    }
    res = 1ll * res *
          ksm(k, 1ll * n * m - 2ll * c.first * c.second +
                     1ll * d.first * d.second) %
          mo;
    n = c.first;
    m = c.second;
    c = d;
    if (c.first == 0) {
      doit = 0;
      res = 1ll * res * ksm(k, 1ll * n * m) % mo;
    }
  }
  printf("%d\n", res);
}

### Prompt

Please formulate a CPP solution to 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>
using namespace std;
int n, m, k, res;
const int mo = 1000000007;
pair<int, int> a, b, c, d;
int ksm(int x, long long y) {
  int ans = 1;
  while (y) {
    if (y & 1) ans = 1ll * ans * x % mo;
    x = 1ll * x * x % mo;
    y = y / 2;
  }
  return ans;
}
int main() {
  res = 1;
  scanf("%d%d%d%d%d", &n, &m, &k, &c.first, &c.second);
  scanf("%d%d%d%d", &a.first, &a.second, &b.first, &b.second);
  if (a > b) swap(a, b);
  int doit = 1;
  while (doit) {
    if (a == b) {
      res = 1ll * res * ksm(k, 1ll * n * m);
      break;
    }
    d = make_pair(0, 0);
    if (a.first + c.first - 1 >= b.first) {
      if (a.second <= b.second && a.second + c.second - 1 >= b.second) {
        d = make_pair(a.first + c.first - b.first,
                      a.second + c.second - b.second);
      } else if (a.second >= b.second && b.second + c.second - 1 >= a.second) {
        d = make_pair(a.first + c.first - b.first,
                      b.second + c.second - a.second);
        b.second = a.second;
        a.second = a.second + c.second - d.second;
      }
    }
    res = 1ll * res *
          ksm(k, 1ll * n * m - 2ll * c.first * c.second +
                     1ll * d.first * d.second) %
          mo;
    n = c.first;
    m = c.second;
    c = d;
    if (c.first == 0) {
      doit = 0;
      res = 1ll * res * ksm(k, 1ll * n * m) % mo;
    }
  }
  printf("%d\n", res);
}

```