← 返回题目列表

Codeforces · 708/E

E. 学生营

中文机器翻译题面 查看原题

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}$$