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;
  using ld = long double;
  using ll = long long;
  ll mod = 1e9 + 7;
  int const N = 3e5 + 100;
  mt19937 rnd;
  ll random(ll limit) {
    uniform_int_distribution<ll> uniform_dist(0, limit);
    return uniform_dist(rnd);
  }
  ll bpow(ll a, ll p) {
    ll res = 1;
    while (p > 0) {
      if (p % 2) {
        res = (res * a) % mod;
      }
      a = (a * a) % mod;
      p /= 2;
    }
    return res;
  }
  ll inv(ll a) { return bpow(a, mod - 2); }
  void solve() {
    ll n, m, k, r, c;
    cin >> n >> m >> k >> r >> c;
    ll x1, x2, y1, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    ll dx = min(abs(x1 - x2), c);
    ll dy = min(abs(y1 - y2), r);
    ll num1 = dx * r + dy * (c - dx);
    if (dx == 0 && dy == 0) {
      num1 = r * c;
    } else if (dx == 0) {
      num1 = c * dy;
    } else if (dy == 0)
      num1 = r * dx;
    ll x3 = max(x1, x2);
    ll x4 = min(x1 + c, x2 + c);
    ll y3 = max(y1, y2);
    ll y4 = min(y1 + r, y2 + r);
    ll num3 = (x4 - x3) * (y4 - y3);
    if (y4 <= y3 || x4 <= x3) num3 = 0;
    ll num2 = n * m - (2 * r * c - num3);
    ll num = num1 + num2;
    ll ans = bpow(k, num);
    cout << ans << '\n';
  }
  int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    rnd = mt19937(956231);
    int t;
    t = 1;
    while (t--) {
      solve();
    }
  }
  