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>  
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;   
using namespace std;
typedef long long ll;
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 

ll ans = 0;
const ll M = 1e9 + 7;

long long modpow(long long a, long long b) {
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a%M;
        a = a * a%M;
        b >>= 1;
    }
    return res;
}

void solve(ll height, ll width, ll sub_height, ll sub_width){
    if(sub_height <= 0 || sub_width<=0){
        ans += height*width;
        ans %= M-1;
        return;
    }
    
    ll n = height;
    ll m = width;
    ll r = sub_height;
    ll c = sub_width;
    ll tmp = 2*r*c;
    pair<ll,ll> a,b;
    a.first = 1,a.second = 1;
    b.first = height - sub_height + 1, b.second = width - sub_width + 1;
    if(a>b)
        swap(a,b);
    //cout<<"Height is "<<height<<" sub_height is "<<sub_height<<" width is "<<width<<" subwidth is "<<sub_width<<endl;
    //cout<<"n is "<<n<<" m is "<<m<<" a is "<<"("<<a.first<<","<<a.second<<") b is ("<<b.first<<","<<b.second<<")\n";
    //cout<<"r is "<<r<<" c is "<<c<<endl;
    ll sub_height2 = a.first + r - b.first;
    ll sub_width2 = (a.second < b.second)?(a.second+c-b.second):(b.second + c - a.second);
    sub_width2 = max(sub_width2, (ll)0);
    tmp -= sub_height2*sub_width2;
    ans += n*m - tmp;
    ans %= M-1;
    solve(r,c,sub_height2,sub_width2);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    ll n,m,k,r,c;
    cin>>n>>m>>k>>r>>c;
    pair<ll,ll> a,b;
    cin>>a.first>>a.second>>b.first>>b.second;
    if(a>b)
        swap(a,b);
    if(a.first == b.first && a.second == b.second){
        cout<<modpow(k, n*m)<<endl;
        return 0;
    }
    ll tmp = 2*r*c;
    ll sub_height = a.first + r - b.first;
    ll sub_width = (a.second < b.second)?(a.second+c-b.second):(b.second + c - a.second);
    sub_width = max(sub_width, (ll)0);
    tmp -= sub_height*sub_width;
    ans = n*m%(M-1)  + M-1- tmp%(M-1);
    ans %=M-1;
    solve(r,c, sub_height,sub_width);
    //cout<<ans<<endl;
    cout<<modpow(k,ans)<<endl;


    return 0;
}