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>
using namespace std;
template<class T,class S=T>inline bool umin(T&m,const S&x){return x<m?m=x,1:0;}
template<class T,class S=T>inline bool umax(T&m,const S&x){return m<x?m=x,1:0;}
auto operator<<(ostream&o,const auto&v)->enable_if_t<!is_constructible_v<string,decltype(v)>,decltype(o<<*end(v))>{int f=0,u=&o==&cerr&&o<<"[";for(auto&&x:v)(f++?o<<(u?", ":" "):o)<<x;return u?o<<"]":o;}
auto operator<<(ostream&o,const auto&t)->decltype(o<<get<0>(t)){o<<"<";apply([&o](auto&...x){int f=0;(((f++?o<<", ":o)<<x),...);},t);return o<<">";}
#ifdef BIZON
	#define rr(...) [](auto&&...x){ cerr << boolalpha << "\e[1;38;5;68m" << #__VA_ARGS__ << " "; int _=0; ((cerr<<"\e[0;38;5;61m"<<",="[!_++]<<"\e[0m "<<x),...)<<endl; }(__VA_ARGS__);
#else
	#define rr(...) 0;
	#define endl '\n'
#endif
#define ALL(c) begin(c), end(c)
#define fun(T, name, ...) function<T(__VA_ARGS__)> name = [&](__VA_ARGS__)->T
#define II(...) __VA_ARGS__; [](auto&...x){(cin>>...>>x);}(__VA_ARGS__);
#define ii(...) int II(__VA_ARGS__)
using ll = long long;

int inv_mod(int a, int m){
	assert(0<a);
	assert(a<m);
	return a==1 ? 1 : m-m*int64_t(inv_mod(m%a, a))/a;
}

template<int mod> struct modint {
	modint(): x(0) {}
	modint(const auto &val): x(val%mod) { if(x<0) x+=mod; }
	static int get_mod() { return mod; }
	void operator+=(const modint &b){ x+=b.x; if(x>=mod) x-=mod; }
	void operator-=(const modint &b){ x-=b.x; if(x<0) x+=mod; }
	void operator*=(const modint &b){ x = int64_t(x)*b.x %mod; }
	void operator/=(const modint &b){ x = int64_t(x)*inv_mod(b.x,mod) %mod; }
	friend modint operator+(modint a, const modint &b){ a+=b; return a; }
	friend modint operator-(modint a, const modint &b){ a-=b; return a; }
	friend modint operator*(modint a, const modint &b){ a*=b; return a; }
	friend modint operator/(modint a, const modint &b){ a/=b; return a; }
	friend modint operator-(modint a){ if(a.x) a.x = mod - a.x; return a; }
	friend modint pow(modint a, uint64_t n) { modint p=1; for(; n; n>>=1, a*=a) if(n&1) p*=a; return p; }
	friend bool operator==(const modint &a, const modint &b){ return a.x==b.x; }
	friend bool operator!=(const modint &a, const modint &b){ return a.x!=b.x; }
	friend ostream& operator<<(ostream &o, const modint &m){ return o<<m.x; }
	explicit operator int(){ return x; }
	private: int x;
};
using mint = modint<(int)1e9+7>;
mint operator""m(unsigned long long x){ return mint(x); }


int main() {
	if(auto f="in.txt"; fopen(f,"r") && freopen(f,"r",stdin));
	cin.tie(0)->sync_with_stdio(0);
	
	ll II(n, m, k, r, c)
	ll II(ax, ay, bx, by)
	
	ll cw = min(ax+r-1, bx+r-1) - max(ax, bx) + 1;
	umax(cw, 0);
	
	ll ch = min(ay+c-1, by+c-1) - max(ay, by) + 1;
	umax(ch, 0);
	
	ll cross = cw * ch;
	rr(cw, ch, cross)
	
	ll common = r*c*2 - cross;
	ll out = n * m - common;
	
	mint ans = pow(mint(k), out + r*c-cross);
	cout<<ans<<endl;
	
	return 0;
}
