#include <bits/stdc++.h>
using namespace std;
template <int MOD, int RT>
struct Mint {
  static const int mod = MOD;
  static constexpr Mint rt() { return RT; }
  static constexpr int md() { return MOD; }
  int v;
  explicit operator int() const { return v; }
  explicit operator bool() const { return v != 0; }
  Mint() { v = 0; }
  Mint(long long _v) {
    v = int((-MOD <= _v && _v < MOD) ? _v : _v % MOD);
    if (v < 0) v += MOD;
  }
  friend bool operator==(const Mint& a, const Mint& b) { return a.v == b.v; }
  friend bool operator!=(const Mint& a, const Mint& b) { return !(a == b); }
  friend bool operator<(const Mint& a, const Mint& b) { return a.v < b.v; }
  friend bool operator>(const Mint& a, const Mint& b) { return a.v > b.v; }
  friend bool operator<=(const Mint& a, const Mint& b) { return a.v <= b.v; }
  friend bool operator>=(const Mint& a, const Mint& b) { return a.v >= b.v; }
  friend std::istream& operator>>(std::istream& in, Mint& a) {
    long long x;
    std::cin >> x;
    a = Mint(x);
    return in;
  }
  friend std::ostream& operator<<(std::ostream& os, const Mint& a) {
    return os << a.v;
  }
  Mint& operator+=(const Mint& m) {
    if ((v += m.v) >= MOD) v -= MOD;
    return *this;
  }
  Mint& operator-=(const Mint& m) {
    if ((v -= m.v) < 0) v += MOD;
    return *this;
  }
  Mint& operator*=(const Mint& m) {
    v = (long long)v * m.v % MOD;
    return *this;
  }
  Mint& operator/=(const Mint& m) { return (*this) *= inv(m); }
  friend Mint pow(Mint a, long long p) {
    Mint ans = 1;
    assert(p >= 0);
    for (; p; p /= 2, a *= a)
      if (p & 1) ans *= a;
    return ans;
  }
  friend Mint inv(const Mint& a) {
    assert(a.v != 0);
    return pow(a, MOD - 2);
  }
  Mint operator-() const { return Mint(-v); }
  Mint& operator++() { return *this += 1; }
  Mint& operator--() { return *this -= 1; }
  friend Mint operator+(Mint a, const Mint& b) { return a += b; }
  friend Mint operator-(Mint a, const Mint& b) { return a -= b; }
  friend Mint operator*(Mint a, const Mint& b) { return a *= b; }
  friend Mint operator/(Mint a, const Mint& b) { return a /= b; }
};
using mi = Mint<1000000007, 5>;
int main() {
  long long n, m, k, r, c;
  cin >> n >> m >> k >> r >> c;
  int w, x, y, z;
  cin >> w >> x >> y >> z;
  mi ans;
  if (w == y && x == z) {
    ans = pow(mi(k), n * m);
  } else {
    ans = pow(mi(k), n * m - r * c);
  }
  cout << ans << '\n';
  return 0;
}

### Prompt

Construct a cpp code solution to the problem outlined:

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;
template <int MOD, int RT>
struct Mint {
  static const int mod = MOD;
  static constexpr Mint rt() { return RT; }
  static constexpr int md() { return MOD; }
  int v;
  explicit operator int() const { return v; }
  explicit operator bool() const { return v != 0; }
  Mint() { v = 0; }
  Mint(long long _v) {
    v = int((-MOD <= _v && _v < MOD) ? _v : _v % MOD);
    if (v < 0) v += MOD;
  }
  friend bool operator==(const Mint& a, const Mint& b) { return a.v == b.v; }
  friend bool operator!=(const Mint& a, const Mint& b) { return !(a == b); }
  friend bool operator<(const Mint& a, const Mint& b) { return a.v < b.v; }
  friend bool operator>(const Mint& a, const Mint& b) { return a.v > b.v; }
  friend bool operator<=(const Mint& a, const Mint& b) { return a.v <= b.v; }
  friend bool operator>=(const Mint& a, const Mint& b) { return a.v >= b.v; }
  friend std::istream& operator>>(std::istream& in, Mint& a) {
    long long x;
    std::cin >> x;
    a = Mint(x);
    return in;
  }
  friend std::ostream& operator<<(std::ostream& os, const Mint& a) {
    return os << a.v;
  }
  Mint& operator+=(const Mint& m) {
    if ((v += m.v) >= MOD) v -= MOD;
    return *this;
  }
  Mint& operator-=(const Mint& m) {
    if ((v -= m.v) < 0) v += MOD;
    return *this;
  }
  Mint& operator*=(const Mint& m) {
    v = (long long)v * m.v % MOD;
    return *this;
  }
  Mint& operator/=(const Mint& m) { return (*this) *= inv(m); }
  friend Mint pow(Mint a, long long p) {
    Mint ans = 1;
    assert(p >= 0);
    for (; p; p /= 2, a *= a)
      if (p & 1) ans *= a;
    return ans;
  }
  friend Mint inv(const Mint& a) {
    assert(a.v != 0);
    return pow(a, MOD - 2);
  }
  Mint operator-() const { return Mint(-v); }
  Mint& operator++() { return *this += 1; }
  Mint& operator--() { return *this -= 1; }
  friend Mint operator+(Mint a, const Mint& b) { return a += b; }
  friend Mint operator-(Mint a, const Mint& b) { return a -= b; }
  friend Mint operator*(Mint a, const Mint& b) { return a *= b; }
  friend Mint operator/(Mint a, const Mint& b) { return a /= b; }
};
using mi = Mint<1000000007, 5>;
int main() {
  long long n, m, k, r, c;
  cin >> n >> m >> k >> r >> c;
  int w, x, y, z;
  cin >> w >> x >> y >> z;
  mi ans;
  if (w == y && x == z) {
    ans = pow(mi(k), n * m);
  } else {
    ans = pow(mi(k), n * m - r * c);
  }
  cout << ans << '\n';
  return 0;
}

```