Uniform Submatrix Sampling in the Divine Matrix

An ancient deity decreed that instead of using a pointer, the divine basketball artist shall construct an infinite matrix, whose entries are defined by

\(a[i][j]= i \oplus j\),

where \(i\) and \(j\) are non‐negative integers and \(\oplus\) denotes the bitwise XOR operation.

Now, consider a submatrix of this infinite matrix with its top–left corner at \((lx,\,ly)\) and bottom–right corner at \((rx,\,ry)\). From this submatrix, one performs \(K\) (\(K \le 10^9\)) independent random samplings; in each sampling a submatrix of size \(W \times H\) is chosen uniformly at random (that is, all top–left positions which allow a full \(W \times H\) block inside the given submatrix are equally likely).

Your task is to compute the probability that all \(K\) chosen \(W \times H\) submatrices are exactly identical. Since the answer may be very small, output it modulo \(10^9+7\). Note that the answer is a rational number; it can be uniquely represented modulo \(10^9+7\) according to Fermat's little theorem.

Note: For most choices of \(W, H\) the mapping from the position of the top–left corner to the resulting \(W \times H\) submatrix is injective (that is, different positions produce distinct content). The only exception is when \(W=H=1\) (i.e. the sampled submatrix is a single element), in which case different positions can yield the same value since \(i \oplus j\) is not an injective function over \(\mathbb{N}^2\). In the non–injective case you must sum over the frequencies.

---

Input Format

The input consists of a single line containing seven space–separated integers:

(lx;; ly;; rx;; ry;; W;; H;; K).

---

Output Format

Output a single integer: the desired probability modulo \(10^9+7\).

---

Recall that if there are \(T\) valid top–left positions in the given submatrix (so that a full \(W \times H\) submatrix fits), and if each possible submatrix (or its content) appears with frequency \(f_s\) (with \(\sum_s f_s = T\)), then the probability that all \(K\) randomly chosen submatrices are identical is

[ P = \frac{\sum_s f_s^K}{T^K} \pmod{10^9+7}. ]

In the injective case (which happens when \((W,H) \neq (1,1)\)), we have \(f_s=1\) for every submatrix \(s\) and \(T\) distinct submatrices, so the answer simplifies to

[ P = \frac{T}{T^K} = \frac{1}{T^{K-1}} \pmod{10^9+7}. ]

</p>

inputFormat

The input consists of a single line with seven integers: lx ly rx ry W H K, where

• lx, ly, rx, ry describe the submatrix of the divine matrix under consideration (with indices starting from 0),
• W and H specify the width and height of the randomly sampled submatrix,
• K is the number of independent samplings.

You may assume that the sampled \(W \times H\) submatrix fits inside the given submatrix, i.e. \(rx - lx + 1 \ge W\) and \(ry - ly + 1 \ge H\).

outputFormat

Output a single integer – the probability that all \(K\) randomly chosen \(W \times H\) submatrices are identical, modulo \(10^9+7\).

sample

1 1 2 2 1 1 2

500000004