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>
#define int long long
using namespace std;

const int mod = 1e9 + 7;
inline int add (int x, int y) {return x + y >= mod ? x + y - mod : x + y;}
inline int mul (int x, int y) {return 1LL * x * y % mod;}
inline int qpm (int x, long long y) {
    int r = 1;
    while (y) {
        if (y & 1) r = mul(r, x);
        x = mul (x, x);
        y >>= 1;
    }
    return r;
}

long long n, m, r, c, k;
long long x1, x2, y1, y2;

signed main()
{
    scanf ("%lld %lld %lld %lld %lld", &n, &m, &k, &r, &c);
    scanf ("%lld %lld %lld %lld", &x1, &y1, &x2, &y2);
    if (x1 > x2) {
        swap (x1, x2);
    }
    if (y1 > y2) {
        swap (y1, y2);
    }
    long long sx, sy, ex, ey;
    if (x1 + r - 1 < x2 || y1 + c - 1 < y2) {
        long long c1 = n * m, c2 = r * c;
        c1 -= c2 * 2;
        int ans = mul(qpm(k, c1), qpm(k, c2));
        printf ("%lld\n", ans);
    }
    else {
        sx = x2; sy = y2;
        ex = x1 + r - 1; ey = y1 + c - 1;
        long long len1 = ex - sx + 1, len2 = ey - sy + 1;
        long long c1 = n * m, c2 = r * c, c3 = len1 * len2;
        if (len1 * 2 > r && len2 * 2 > c) {
            // long long a = __gcd(len1, r), b = __gcd(len2, c);
            // long long A = ex - x1 + 1, B = ey - y1 + 1;
            int temp = qpm(k, c2 - c3);
            c1 = c1 - (c2 * 2 - c3);
            int ans = mul (qpm(k, c1), temp);
            printf ("%lld\n", ans);
        }
        else {
            c2 -= 2 * c3;
            c1 -= 3 * c3 + c2 * 2;
            int ans = mul(mul(qpm(k, c1), qpm(k, c2)), qpm(k, c3));
            printf ("%lld\n", ans);
        }
    }
    return 0;
}
