CF708E.Student's Camp

Alex studied well and won the trip to student camp Alushta, located on the seashore.

Unfortunately, it's the period of the strong winds now and there is a chance the camp will be destroyed! Camp building can be represented as the rectangle of n + 2 concrete blocks height and m blocks width.

Every day there is a breeze blowing from the sea. Each block, except for the blocks of the upper and lower levers, such that there is no block to the left of it is destroyed with the probability . Similarly, each night the breeze blows in the direction to the sea. Thus, each block (again, except for the blocks of the upper and lower levers) such that there is no block to the right of it is destroyed with the same probability p. Note, that blocks of the upper and lower level are indestructible, so there are only n·m blocks that can be destroyed.

The period of the strong winds will last for k days and k nights. If during this period the building will split in at least two connected components, it will collapse and Alex will have to find another place to spend summer.

Find the probability that Alex won't have to look for other opportunities and will be able to spend the summer in this camp.

亚历克斯学习刻苦，赢得了前往位于海滨的阿尔什塔学生夏令营的机会。

不幸的是，目前正值强风期，夏令营营地有被摧毁的风险！营地建筑可建模为一个高为 $n + 2$ 个混凝土方块、宽为 $m$ 个方块的矩形。

每天白天，海风从海上吹来。除最上层和最下层的方块外，所有左侧无方块的方块均以概率 被摧毁。类似地，每晚海风朝向大海方向吹拂。因此，除最上层和最下层的方块外，所有右侧无方块的方块也以相同概率 $p$ 被摧毁。注意：最上层与最下层的方块不可摧毁，故仅有 $n \cdot m$ 个方块可能被摧毁。

强风期将持续 $k$ 天和 $k$ 夜。若在此期间建筑物分裂为至少两个连通块，则建筑将坍塌，亚历克斯不得不另寻他处度过暑假。

求亚历克斯无需另寻他处、得以在该营地度过暑假的概率。

The first line of the input contains two integers n and m (1 ≤ n, m ≤ 1500) that define the size of the destructible part of building.

The second line of the input contains two integers a and b (1 ≤ a ≤ b ≤ 109) that define the probability p. It's guaranteed that integers a and b are coprime.

The third line contains a single integer k (0 ≤ k ≤ 100 000) — the number of days and nights strong wind will blow for.

输入的第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 1500$），表示建筑物可破坏部分的尺寸。

输入的第二行包含两个整数 $a$ 和 $b$（$1 \leq a \leq b \leq 10^9$），用于定义概率 $p$。保证整数 $a$ 和 $b$ 互质。

输入的第三行包含一个整数 $k$（$0 \leq k \leq 100\,000$）——强风将持续吹拂的天数与夜晚数。

Consider the answer as an irreducible fraction is equal to . Print one integer equal to . It's guaranteed that within the given constraints .

将答案视为一个最简分数，其值等于 。输出一个整数，其值等于 。在给定约束条件下，保证 。

In the first sample, each of the four blocks is destroyed with the probability . There are 7 scenarios that result in building not collapsing, and the probability we are looking for is equal to , so you should print

在第一个样例中，四个方块各自被摧毁的概率均为 。共有 7 种情形使得建筑不会倒塌，所求概率为 ，因此你应输出