description: 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>
solution: #include <bits/stdc++.h>
  using namespace std;
  const long long linf = 4000000000000000000LL;
  const long long inf = 1000000007;
  void pv(vector<int> a) {
    for (auto& x : a) cout << x << " ";
    cout << '\n';
  }
  void pv(vector<long long> a) {
    for (auto& x : a) cout << x << " ";
    cout << '\n';
  }
  void pv(vector<vector<int> > a) {
    for (int i = (0); i < (int(a.size())); ++i) {
      cout << i << '\n';
      pv(a[i]);
      cout << '\n';
    }
  }
  void pv(vector<vector<long long> > a) {
    for (int i = (0); i < (int(a.size())); ++i) {
      cout << i << '\n';
      pv(a[i]);
    }
    cout << '\n';
  }
  void pv(vector<string> a) {
    for (auto& x : a) cout << x << '\n';
    cout << '\n';
  }
  void setIO(string second) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
  }
  template <int MOD, int RT>
  struct mint {
    static const int mod = MOD;
    static constexpr mint rt() { return RT; }
    int v;
    explicit operator int() const { return v; }
    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; }
    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 = int((long long)v * m.v % MOD);
      return *this;
    }
    mint& operator/=(const mint& m) { return (*this) *= inv(m); }
    friend mint power(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 power(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; }
  };
  int main() {
    setIO("test1");
    int n, m, k, r, c, ax, ay, bx, by;
    cin >> n >> m >> k >> r >> c >> ax >> ay >> bx >> by;
    cout << (int)power(
        (mint<inf, 5>)k,
        (long long)n * m - (ax == bx && ay == by ? 0 : (long long)r * c));
  }
  