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;
  static char ibuf[1 << 20];
  char *fis = ibuf, *fit = ibuf;
  inline char readChar() {
    return fis == fit && (fit = (fis = ibuf) + fread(ibuf, 1, 1 << 20, stdin),
                          fis == fit)
               ? EOF
               : *fis++;
  }
  inline int read() {
    char c, _c;
    int x;
    for (c = readChar(); !isdigit(c); c = readChar())
      ;
    for (x = 0; isdigit(c); c = readChar()) {
      x = x * 10 + c - '0';
    }
    return x;
  }
  static char ostc[100], obuf[1 << 20];
  int ol = 0;
  char *fos = obuf, *fot = obuf + (1 << 20) - 1;
  inline void writeChar(char c) {
    *fos++ = c;
    if (fos == fot) {
      fwrite(obuf, 1, fos - obuf, stdout);
      fos = obuf;
    }
  }
  inline void write(int n, char c) {
    if (!n) {
      writeChar('0');
    } else {
      while (n) {
        ostc[++ol] = n % 10 + 48, n /= 10;
      }
    }
    for (; ol; ol--) {
      writeChar(ostc[ol]);
    }
    writeChar(c);
  }
  const int mod = 1e9 + 7;
  int qpow(int x, long long times) {
    int res = 1;
    while (times) {
      if (times & 1) res = 1LL * res * x % mod;
      x = 1LL * x * x % mod;
      times >>= 1;
    }
    return res;
  }
  int main() {
    int n, m, k, r, c;
    int ax, ay, bx, by;
    scanf("%d%d%d%d%d", &n, &m, &k, &r, &c);
    scanf("%d%d%d%d", &ax, &ay, &bx, &by);
    if (ax == bx && ay == by)
      printf("%d\n", qpow(k, 1LL * n * m));
    else
      printf("%d\n", qpow(k, 1LL * n * m - 1LL * r * c));
  }
  