题目描述

Alex 学习刻苦，赢得了前往位于海边的学生营地 Alushta 的旅行机会。

不幸的是，现在正值大风期，营地有可能被毁坏！营地建筑可以看作是由 $n+2$ 层高、$m$ 列宽的混凝土块组成的矩形。

每天都有来自海上的微风。每一块（除了最上层和最下层的那些），如果它左边没有块，则会以概率 $p$ 被摧毁。同理，每晚微风会朝向大海吹去。于是，每一块（同样除了最上层和最下层的那些），如果其右侧没有块，也会以相同的概率 $p$ 被摧毁。注意，最上层和最下层的混凝土块是不可摧毁的，因此只有 $n · m$ 个块有可能被摧毁。

强风期会持续 $k$ 天与 $k$ 夜。如果在此期间，建筑分裂成至少两个连通块，则会倒塌，Alex 只能另找地方度过夏天。

请你计算，Alex 不必另寻他处、能够顺利于该营地度夏的概率。

输入格式

第一行包含两个整数 $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 100000$）——表示大风将持续的天数和夜数。

输出格式

假设答案为最简分数 $\frac{x}{y}$，请输出一个整数 $z$，使得 $0 \le z < 10^9 + 7$，且满足 $z \equiv x \times y^{-1} \pmod {10^9 + 7}$。保证在数据范围内上述数一定存在。

输入输出样例 #1

输入 #1

2 2
1 2
1

输出 #1

937500007

输入输出样例 #2

输入 #2

5 1
3 10
1

输出 #2

95964640

输入输出样例 #3

输入 #3

3 3
1 10
5

输出 #3

927188454

说明/提示

在第一个样例中，四块砖每块被摧毁的概率为 $\frac{1}{2}$。有 $7$ 种情况不会使建筑倒塌，所求概率为 $\frac{7}{16}$，因此应输出 $7 \times 16^{-1} \bmod (10^9 + 7)=937500007$。

由 ChatGPT 5 翻译