Alex学习出色,赢得了前往位于海边的阿卢什塔学生营的机会。
不幸的是,现在正是大风时期,营地有可能被摧毁!营地建筑可以表示为 n + 2 个混凝土块高、m 个块宽的矩形。
每天都有海风吹来。除了上杠杆和下杠杆的块之外,每个块都以 $$p = \frac{a}{b}$$ 的概率被破坏,这样其左侧没有块。同样,每天晚上微风都吹向大海的方向。因此,每个块(同样,除了上杠杆和下杠杆的块之外),其右侧没有块的情况下,都会以相同的概率 p 被破坏。注意,上层和下层的块都是不可破坏的,因此只有n·m个块可以被破坏。
强风周期将持续k天k夜。如果在此期间建筑物分裂成至少两个相连的部分,它将倒塌,亚历克斯将不得不寻找另一个地方来度过夏天。
求 Alex 无需寻找其他机会就能在这个营地度过夏天的概率。
输入
输入的第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 1500),它们定义建筑物可破坏部分的大小。
输入的第二行包含两个整数 a 和 b (1 ≤ a ≤ b ≤ 109),它们定义概率 p。保证整数 a 和 b 互质。
第三行包含一个整数 k (0 ≤ k ≤ 100 000) — 强风吹的天数和夜数。
输出
将答案视为不可约分数等于 $$\frac{c}{d}$$。打印一个等于 $$c \cdot d^{-1} \mod 10^{9} + 7$$ 的整数。保证在给定的约束条件下 $$d \neq 0 \pmod{10^9 + 7}$$。
示例
输入 #1
2 2 1 2 1
输出 #1
937500007
输入 #2
5 1 3 10 1
输出 #2
95964640
输入 #3
3 3 1 10 5
输出 #3
927188454
注意
在第一个样本中,四个块中的每一个都以 $$\frac{1}{2}$$ 的概率被破坏。有 7 种情况会导致建筑物不倒塌,我们要寻找的概率等于 $$\frac{7}{16}$$,因此您应该打印 $$7 \cdot 16^{-1} = 7 \cdot 562500004 = 937500007 \pmod {10^9 + 7}$$