N. Moving grid
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

We got some leaks from the most dangerous place ever [Not Safe] that Baraa hates long statements.

So we decided not to write a story for this problem :D.

Given $$$N\times M$$$ points on a two dimensional-grid with coordinates $$$(x_i,y_j)=(a\times i,b\times j)$$$ where a,b are given integer values and for all possible pairs $$$i,j(1\le i\le N,1\le j\le M)$$$.

Each second exactly one action will happen, either all points will move down simultaneously or they will move left simultaneously, and the action will happen randomly with a probability of $$$\frac{1}{2}$$$.

Points on-axis OX can't move down anymore even if the action was moving all points down, the same goes for points on axis OY that they can't move left if the action was moving all points left.

In other words, if the action is move down, all points with coordinates $$$(x,y)$$$ where $$$(y>0)$$$ will move to the position $$$(x,y-1)$$$. And if the action is move left, all points with coordinates $$$(x,y)$$$ where $$$(x>0)$$$ will move to the position $$$(x-1,y)$$$.

Note that More than one point can have the same coordinates at the same time.

When a point has a coordinate $$$(0,0)$$$ it will disappear instantly.

$$$K$$$ actions happened, and you are now asked the expected number of points that still exist on the grid.

Input

The first line contains one integer $$$T$$$, the number of test cases.

Each of the following $$$T$$$ lines contains $$$5$$$ integers $$$N, M,a,b,K$$$ $$$(1\le N,M,a,b\le 10^9,0\le K\le 2\times 10^5)$$$ Where $$$N,M$$$ determine the number of points in the grid, $$$a,b$$$ determine the coordinates of the points and $$$K$$$ represents the number of moves.

The sum of $$$K$$$ over all test cases doesn't exceed $$$2\cdot 10^5$$$.

Output

Print the expected number of points that still exist on the grid modulo $$$10^9+7$$$.

Formally, let $$$MOD=10^9+7$$$. It can be demonstrated that the answer can be presented as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q\not\equiv0(\mod MOD)$$$.

Output a single integer equal to $$$(p\times q^{-1})\mod MOD$$$. In other words, output an integer $$$x$$$ such that $$$0\le x< M$$$ and $$$x\times q\equiv p(\mod MOD)$$$.

Example
Input
3
1 1 1 1 1
1 1 1 1 2
5 4 2 3 7
Output
1
500000004
140625020