Dệt Batik

Cho một tấm vải hình lưới kích thước $n\times m$. Mỗi ô của lưới được tô bằng một trong $k$ màu.

Một hình chữ nhật con được xác định bởi ô góc trên-trái và ô góc dưới-phải của nó. Hai hình chữ nhật con được gọi là cùng hoa văn nếu chúng có cùng chiều rộng, cùng chiều cao, và với mọi cặp vị trí tương ứng $(i,j)$, ô ở vị trí đó trong hình chữ nhật thứ nhất có cùng màu với ô tương ứng trong hình chữ nhật thứ hai.

Xét hai hình chữ nhật con, cả hai đều có kích thước $r$ hàng và $c$ cột:

• Hình thứ nhất có góc trên-trái tại ô $(a_x,a_y)$.
• Hình thứ hai có góc trên-trái tại ô $(b_x,b_y)$.

Hãy đếm số cách tô màu toàn bộ lưới sao cho hai hình chữ nhật con này cùng hoa văn. In kết quả theo modulo ${10}^9+7$.

Dữ liệu vào

• Dòng đầu chứa năm số nguyên $n$, $m$, $k$, $r$, $c$ — kích thước lưới, số màu, và kích thước (số hàng $\times$ số cột) của hình chữ nhật con.
• Dòng thứ hai chứa bốn số nguyên $a_x$, $a_y$, $b_x$, $b_y$ — tọa độ góc trên-trái của hình chữ nhật thứ nhất và thứ hai. Cả hai hình chữ nhật đều nằm hoàn toàn bên trong lưới.

Dữ liệu ra

Một số nguyên duy nhất là số cách tô màu thỏa mãn, theo modulo ${10}^9+7$.

Ràng buộc

• $1\le n,m\le {10}^9$
• $1\le k\le {10}^9$
• $1\le r\le min({10}^6,n)$, $1\le c\le min({10}^6,m)$
• $1\le a_x,b_x\le n$; $1\le a_y,b_y\le m$
• $a_x+r-1\le n$, $b_x+r-1\le n$, $a_y+c-1\le m$, $b_y+c-1\le m$

Ví dụ