#include <bits/stdc++.h>
using namespace std;
template <class c>
struct rge {
  c b, e;
};
template <class c>
rge<c> range(c i, c j) {
  return rge<c>{i, j};
}
template <class c>
auto dud(c* x) -> decltype(cerr << *x, 0);
template <class c>
char dud(...);
struct debug {
  template <class c>
  debug& operator<<(const c&) {
    return *this;
  }
};
const int mxn = 1e5;
const long long mod = 1e9 + 7;
long long n, m, k, r, c, ax, ay, bx, by;
long long fastexpo(long long a, long long b) {
  long long ret = 1;
  while (b) {
    if (b & 1) {
      ret = (ret * a) % mod;
    }
    a = (a * a) % mod;
    b >>= 1;
  }
  return ret;
}
long long solve(long long n1, long long m1, long long k1, long long r1,
                long long c1, long long ax1, long long ay1, long long bx1,
                long long by1) {
  if (n1 == 1 && m1 == 1) {
    return k1;
  } else if (ax1 == bx1 && ay1 == by1) {
    long long ans = fastexpo(k1, n1 * m1);
    return ans;
  } else if (abs(ax1 - bx1) < r1 && abs(ay1 - by1) < c1) {
    bool atas, kanan;
    if (bx1 >= ax1) {
      atas = false;
    } else {
      atas = true;
    }
    if (by1 >= ay1) {
      kanan = true;
    } else {
      kanan = false;
    }
    long long r2, c2;
    if (atas) {
      r2 = bx1 + r1 - ax1;
    } else {
      r2 = ax1 + r1 - bx1;
    }
    if (kanan) {
      c2 = ay1 + c1 - by1;
    } else {
      c2 = by1 + c1 - ay1;
    }
    long long temp;
    if (!kanan && atas) {
      temp = solve(r1, c1, k1, r2, c2, 1ll, 1ll, r1 - r2 + 1, c1 - c2 + 1);
    } else if (!kanan && !atas) {
      temp = solve(r1, c1, k1, r2, c2, r1 - r2 + 1, 1ll, 1ll, c1 - c2 + 1);
    } else if (kanan && !atas) {
      temp = solve(r1, c1, k1, r2, c2, r1 - r2 + 1, c1 - c2 + 1, 1ll, 1ll);
    } else if (kanan && atas) {
      temp = solve(r1, c1, k1, r2, c2, 1ll, c1 - c2 + 1, r1 - r2 + 1, 1ll);
    }
    debug() << "["
            << "temp"
               ": "
            << (temp) << "] ";
    long long ans = fastexpo(k1, n1 * m1 - 2 * r1 * c1 + r2 * c2);
    return (ans * temp) % mod;
  } else {
    long long ans = fastexpo(k1, n1 * m1 - 2 * r1 * c1);
    ans = (ans * fastexpo(k1, r1 * c1)) % mod;
    return ans;
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m >> k >> r >> c >> ax >> ay >> bx >> by;
  cout << solve(n, m, k, r, c, ax, ay, bx, by);
}

### 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;
template <class c>
struct rge {
  c b, e;
};
template <class c>
rge<c> range(c i, c j) {
  return rge<c>{i, j};
}
template <class c>
auto dud(c* x) -> decltype(cerr << *x, 0);
template <class c>
char dud(...);
struct debug {
  template <class c>
  debug& operator<<(const c&) {
    return *this;
  }
};
const int mxn = 1e5;
const long long mod = 1e9 + 7;
long long n, m, k, r, c, ax, ay, bx, by;
long long fastexpo(long long a, long long b) {
  long long ret = 1;
  while (b) {
    if (b & 1) {
      ret = (ret * a) % mod;
    }
    a = (a * a) % mod;
    b >>= 1;
  }
  return ret;
}
long long solve(long long n1, long long m1, long long k1, long long r1,
                long long c1, long long ax1, long long ay1, long long bx1,
                long long by1) {
  if (n1 == 1 && m1 == 1) {
    return k1;
  } else if (ax1 == bx1 && ay1 == by1) {
    long long ans = fastexpo(k1, n1 * m1);
    return ans;
  } else if (abs(ax1 - bx1) < r1 && abs(ay1 - by1) < c1) {
    bool atas, kanan;
    if (bx1 >= ax1) {
      atas = false;
    } else {
      atas = true;
    }
    if (by1 >= ay1) {
      kanan = true;
    } else {
      kanan = false;
    }
    long long r2, c2;
    if (atas) {
      r2 = bx1 + r1 - ax1;
    } else {
      r2 = ax1 + r1 - bx1;
    }
    if (kanan) {
      c2 = ay1 + c1 - by1;
    } else {
      c2 = by1 + c1 - ay1;
    }
    long long temp;
    if (!kanan && atas) {
      temp = solve(r1, c1, k1, r2, c2, 1ll, 1ll, r1 - r2 + 1, c1 - c2 + 1);
    } else if (!kanan && !atas) {
      temp = solve(r1, c1, k1, r2, c2, r1 - r2 + 1, 1ll, 1ll, c1 - c2 + 1);
    } else if (kanan && !atas) {
      temp = solve(r1, c1, k1, r2, c2, r1 - r2 + 1, c1 - c2 + 1, 1ll, 1ll);
    } else if (kanan && atas) {
      temp = solve(r1, c1, k1, r2, c2, 1ll, c1 - c2 + 1, r1 - r2 + 1, 1ll);
    }
    debug() << "["
            << "temp"
               ": "
            << (temp) << "] ";
    long long ans = fastexpo(k1, n1 * m1 - 2 * r1 * c1 + r2 * c2);
    return (ans * temp) % mod;
  } else {
    long long ans = fastexpo(k1, n1 * m1 - 2 * r1 * c1);
    ans = (ans * fastexpo(k1, r1 * c1)) % mod;
    return ans;
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m >> k >> r >> c >> ax >> ay >> bx >> by;
  cout << solve(n, m, k, r, c, ax, ay, bx, by);
}

```