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;
using ll = long long;
using PII = pair<int, int>;
using VI = vector<int>;
#define fst first
#define snd second

void prec() {}

using UINT = unsigned long long;
using ull = unsigned long long;
template <UINT MD>
struct ModInt {
  using M = ModInt;
  static constexpr UINT get_mod() { return MD; }
  const static M G;
  UINT v;
  ModInt(ll _v = 0) { set_v(UINT(_v % MD + MD)); }
  M &set_v(UINT _v) {
    v = (_v < MD) ? _v : _v - MD;
    return *this;
  }
  explicit operator bool() const { return v != 0; }
  M operator-() const { return M() - *this; }
  M operator+(const M &r) const { return M().set_v(v + r.v); }
  M operator-(const M &r) const { return M().set_v(v + MD - r.v); }
  M operator*(const M &r) const { return M().set_v(UINT(ull(v) * r.v % MD)); }
  M operator/(const M &r) const { return *this * r.inv(); }
  M &operator+=(const M &r) { return *this = *this + r; }
  M &operator-=(const M &r) { return *this = *this - r; }
  M &operator*=(const M &r) { return *this = *this * r; }
  M &operator/=(const M &r) { return *this = *this / r; }
  bool operator==(const M &r) const { return v == r.v; }
  M pow(ll n) const {
    M x = *this, r = 1;
    while (n) {
      if (n & 1) r *= x;
      x *= x;
      n >>= 1;
    }
    return r;
  }
  M inv() const { return pow(MD - 2); }
  friend ostream &operator<<(ostream &os, const M &r) { return os << r.v; }
};
using Mint = ModInt<1000'000'007>;

using PLL = pair<ll, ll>;
PLL combine(PLL a, PLL b) { return {max(a.fst, b.fst), min(a.snd, b.snd)}; }

ll len(PLL a) { return max(0ll, a.snd - a.fst + 1); }

void solve() {
  ll n, m, k, r, c, ax, ay, bx, by;
  cin >> n >> m >> k >> r >> c >> ax >> ay >> bx >> by;

  PLL xs = combine({ax, ax + r - 1}, {bx, bx + r - 1});
  PLL ys = combine({ay, ay + c - 1}, {by, by + c - 1});
  ll common = len(xs) * len(ys);
  ll extra = r * c - common;
  ll rest = n * m - 2 * extra - common;

  Mint ans = Mint(k).pow(rest + extra);
  cout << ans << '\n';
}

#ifdef LOCAL_EXEC
#define TEST_CASES
#endif
// #define PRINT_CASE_NUMBERS

/*----- TEMPLATE ----------------------------------------------------------*/
int main(int argc, char *argv[]) {
#ifdef LOCAL_EXEC
  if (!(argc == 2 && string(argv[1]) == "-c")) {
    freopen("sample.in", "r", stdin);
    freopen("sample.out", "w", stdout);
  }
#else
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
#endif

  prec();

  int t = 1;
#ifdef TEST_CASES
  cin >> t;
#endif
  for (int it = 1; it <= t; it++) {
#ifdef PRINT_CASE_NUMBERS
    cout << "Case #" << it << ": ";
#endif
    solve();
  }

  return 0;
}
