#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
template <int MOD>
struct ModInt {
  int val;
  ModInt(ll v = 0) : val(int(v % MOD)) {
    if (val < 0) val += MOD;
  };
  ModInt operator+() const { return ModInt(val); }
  ModInt operator-() const { return ModInt(MOD - val); }
  ModInt inv() const { return this->pow(MOD - 2); }
  ModInt operator+(const ModInt& x) const { return ModInt(*this) += x; }
  ModInt operator-(const ModInt& x) const { return ModInt(*this) -= x; }
  ModInt operator*(const ModInt& x) const { return ModInt(*this) *= x; }
  ModInt operator/(const ModInt& x) const { return ModInt(*this) /= x; }
  ModInt pow(ll n) const {
    auto x = ModInt(1);
    auto b = *this;
    while (n > 0) {
      if (n & 1) x *= b;
      n >>= 1;
      b *= b;
    }
    return x;
  }
  ModInt& operator+=(const ModInt& x) {
    if ((val += x.val) >= MOD) val -= MOD;
    return *this;
  }
  ModInt& operator-=(const ModInt& x) {
    if ((val -= x.val) < 0) val += MOD;
    return *this;
  }
  ModInt& operator*=(const ModInt& x) {
    val = int(ll(val) * x.val % MOD);
    return *this;
  }
  ModInt& operator/=(const ModInt& x) { return *this *= x.inv(); }
  bool operator==(const ModInt& b) const { return val == b.val; }
  bool operator!=(const ModInt& b) const { return val != b.val; }
  friend std::istream& operator>>(std::istream& is, ModInt& x) noexcept {
    return is >> x.val;
  }
  friend std::ostream& operator<<(std::ostream& os, const ModInt& x) noexcept {
    return os << x.val;
  }
};
using mint = ModInt<int(1e9 + 7)>;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, m, k, r, c, ax, ay, bx, by;
  cin >> n >> m >> k >> r >> c >> ax >> ay >> bx >> by;
  if (ax > bx) {
    swap(ax, bx);
    swap(ay, by);
  }
  if (by < ay) {
    int d = ay - by;
    ay = by, by = ay + d;
  }
  assert(ax <= bx && ay <= by);
  if (ax == bx && ay == by) {
    cout << mint(k).pow(ll(n) * m) << endl;
    return 0;
  }
  mint ans = 1;
  for (int i = 0; i < r; i++) {
    int w = (i < bx - ax ? c : min(by - ay, c));
    ans *= mint(k).pow(w);
  };
  ans *= mint(k).pow((ll)n * m - 2 * (ll)r * c +
                     (ll)max(0, c - (by - ay)) * max(0, r - (bx - ax)));
  cout << ans << endl;
}

### Prompt

Please create a solution in cpp 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;
using ll = long long;
using pii = pair<int, int>;
template <int MOD>
struct ModInt {
  int val;
  ModInt(ll v = 0) : val(int(v % MOD)) {
    if (val < 0) val += MOD;
  };
  ModInt operator+() const { return ModInt(val); }
  ModInt operator-() const { return ModInt(MOD - val); }
  ModInt inv() const { return this->pow(MOD - 2); }
  ModInt operator+(const ModInt& x) const { return ModInt(*this) += x; }
  ModInt operator-(const ModInt& x) const { return ModInt(*this) -= x; }
  ModInt operator*(const ModInt& x) const { return ModInt(*this) *= x; }
  ModInt operator/(const ModInt& x) const { return ModInt(*this) /= x; }
  ModInt pow(ll n) const {
    auto x = ModInt(1);
    auto b = *this;
    while (n > 0) {
      if (n & 1) x *= b;
      n >>= 1;
      b *= b;
    }
    return x;
  }
  ModInt& operator+=(const ModInt& x) {
    if ((val += x.val) >= MOD) val -= MOD;
    return *this;
  }
  ModInt& operator-=(const ModInt& x) {
    if ((val -= x.val) < 0) val += MOD;
    return *this;
  }
  ModInt& operator*=(const ModInt& x) {
    val = int(ll(val) * x.val % MOD);
    return *this;
  }
  ModInt& operator/=(const ModInt& x) { return *this *= x.inv(); }
  bool operator==(const ModInt& b) const { return val == b.val; }
  bool operator!=(const ModInt& b) const { return val != b.val; }
  friend std::istream& operator>>(std::istream& is, ModInt& x) noexcept {
    return is >> x.val;
  }
  friend std::ostream& operator<<(std::ostream& os, const ModInt& x) noexcept {
    return os << x.val;
  }
};
using mint = ModInt<int(1e9 + 7)>;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, m, k, r, c, ax, ay, bx, by;
  cin >> n >> m >> k >> r >> c >> ax >> ay >> bx >> by;
  if (ax > bx) {
    swap(ax, bx);
    swap(ay, by);
  }
  if (by < ay) {
    int d = ay - by;
    ay = by, by = ay + d;
  }
  assert(ax <= bx && ay <= by);
  if (ax == bx && ay == by) {
    cout << mint(k).pow(ll(n) * m) << endl;
    return 0;
  }
  mint ans = 1;
  for (int i = 0; i < r; i++) {
    int w = (i < bx - ax ? c : min(by - ay, c));
    ans *= mint(k).pow(w);
  };
  ans *= mint(k).pow((ll)n * m - 2 * (ll)r * c +
                     (ll)max(0, c - (by - ay)) * max(0, r - (bx - ax)));
  cout << ans << endl;
}

```