← 返回题目列表

Codeforces · 963/E

E. 等待的循环

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

将芯片放置在坐标系位于点 (0, 0) 的场地上。

芯片每秒随机移动。如果芯片当前位于点 (x, y),一秒后它会以概率 p1 移动到点 (x - 1, y),以概率 p2 移动到点 (x, y - 1),以概率 p3 移动到点 (x + 1, y),以概率 p4 移动到点 (x, y + 1)。保证 p1 + p2 + p3 + p4 = 1。移动是独立的。

找出芯片离开原点的距离大于 R 的预期时间(即满足 $$x^2 + y^2 > R^2$$)。

输入

第一行包含五个整数 R、a1、a2、a3 和 a4(0 ≤ R ≤ 50、1 ≤ a1、a2、a3、a4 ≤ 1000)。

概率 pi 可以使用公式 $$p_{i} = \frac{a_{i}}{a_{1} + a_{2} + a_{3} + a_{4}}$$ 计算。

输出

可以证明,这个问题的答案始终是 $$\frac{p}{q}$$ 形式的有理数,其中 $$Q \not\equiv 0 \pmod{10^9 + 7}$$。

打印 P·Q - 1 模 109 + 7。

示例

输入 #1

0 1 1 1 1

输出 #1

1

输入 #2

1 1 1 1 1

输出 #2

666666674

输入 #3

1 1 2 1 2

输出 #3

538461545

注意

在第一个示例中,芯片最初位于距原点 0 的距离处。一秒钟内芯片会向某个方向移动到距离1,因此到原点的距离将变为1。

第二个和第三个测试的答案:$$\frac{8}{3}$$ 和 $${ \frac { 3 6 } { 1 3 } }$$。