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 = 1e9 + 7;
long long inv(long long a) {
  long long u = 0, v = 1, b = mod;
  while (a) {
    long long t = b / a;
    b -= t * a, u -= t * v;
    swap(a, b);
    swap(u, v);
  }
  u %= mod;
  if (u < 0) u += mod;
  return u;
}
struct mint {
  int x;
  mint() : x(0) {}
  mint(int x) : x(x) {}
  mint(long long x) : x() {
    if (x >= mod || x < -mod) x %= mod;
    if (x < 0) x += mod;
    this->x = x;
  }
  mint &operator-=(const mint &rhs) {
    x -= rhs.x;
    if (x < 0) x += mod;
    return *this;
  }
  mint &operator+=(const mint &rhs) {
    x += rhs.x;
    if (x >= mod) x -= mod;
    return *this;
  }
  mint &operator*=(const mint &rhs) {
    x = (long long)x * rhs.x % mod;
    return *this;
  }
  mint &operator/=(const mint &rhs) {
    x = (long long)x * inv(rhs.x) % mod;
    return *this;
  }
  bool operator<(const mint &rhs) { return x < rhs.x; }
  bool operator==(const mint &rhs) { return x == rhs.x; }
  bool operator!=(const mint &rhs) { return x != rhs.x; }
  mint operator-() { return mint(-x); }
  friend mint operator+(const mint &lhs, const mint &rhs) {
    mint ret(lhs);
    return ret += rhs;
  }
  friend mint operator-(const mint &lhs, const mint &rhs) {
    mint ret(lhs);
    return ret -= rhs;
  }
  friend mint operator*(const mint &lhs, const mint &rhs) {
    mint ret(lhs);
    return ret *= rhs;
  }
  friend mint operator/(const mint &lhs, const mint &rhs) {
    mint ret(lhs);
    return ret /= rhs;
  }
  friend ostream &operator<<(ostream &os, const mint &rhs) {
    os << rhs.x;
    return os;
  }
  friend istream &operator>>(istream &is, mint &rhs) {
    long long a;
    is >> a;
    rhs = a;
    return is;
  }
};
mint fpow(mint a, long long b) {
  mint r = 1;
  for (; b; b >>= 1) {
    if (b & 1) r = r * a;
    a = a * a;
  }
  return r;
}
int main() {
  int n, m, k, r, c;
  cin >> n >> m >> k >> r >> c;
  int x1, y1, x2, y2;
  cin >> x1 >> y1 >> x2 >> y2;
  long long p = 1ll * n * m - 1ll * r * c;
  cout << fpow(k, p) << endl;
}
