English · Original
Chinese · Translation
Formal · Original
A chip was placed on a field with coordinate system onto point (0, 0).
Every second the chip moves randomly. If the chip is currently at a point (_x_, _y_), after a second it moves to the point (_x_ - 1, _y_) with probability _p_1, to the point (_x_, _y_ - 1) with probability _p_2, to the point (_x_ + 1, _y_) with probability _p_3 and to the point (_x_, _y_ + 1) with probability _p_4. It's guaranteed that _p_1 + _p_2 + _p_3 + _p_4 = 1. The moves are independent.
Find out the expected time after which chip will move away from origin at a distance greater than _R_ (i.e. will be satisfied).
## Input
First line contains five integers _R_, _a_1, _a_2, _a_3 and _a_4 (0 ≤ _R_ ≤ 50, 1 ≤ _a_1, _a_2, _a_3, _a_4 ≤ 1000).
Probabilities _p__i_ can be calculated using formula .
## Output
It can be shown that answer for this problem is always a rational number of form , where .
Print _P_·_Q_ - 1 modulo 109 + 7.
[samples]
## Note
In the first example initially the chip is located at a distance 0 from origin. In one second chip will move to distance 1 is some direction, so distance to origin will become 1.
Answers to the second and the third tests: and .
一个芯片被放置在带有坐标系的场上的点 $(0, 0)$ 处。
每秒，芯片随机移动。如果芯片当前位于点 $(x, y)$，则一秒钟后，它以概率 $p_1$ 移动到点 $(x - 1, y)$，以概率 $p_2$ 移动到点 $(x, y - 1)$，以概率 $p_3$ 移动到点 $(x + 1, y)$，以概率 $p_4$ 移动到点 $(x, y + 1)$。保证 $p_1 + p_2 + p_3 + p_4 = 1$。移动相互独立。
求芯片移动到与原点距离大于 $R$ 所需的期望时间（即满足 $\sqrt{x^2 + y^2} > R$）。
第一行包含五个整数 $R, a_1, a_2, a_3$ 和 $a_4$（$0 ≤ R ≤ 50, 1 ≤ a_1, a_2, a_3, a_4 ≤ 1000$）。
概率 $p_i$ 可通过公式 $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 \cdot Q^{-1}$ 对 $10^9 + 7$ 取模的结果。
在第一个示例中，芯片初始时位于与原点距离为 $0$ 的位置。一秒钟后，芯片会沿某个方向移动到距离为 $1$ 的位置，因此到原点的距离变为 $1$。
第二个和第三个测试用例的答案分别为 $666666674$ 和 $538461545$。
## Input
第一行包含五个整数 $R, a_1, a_2, a_3$ 和 $a_4$（$0 ≤ R ≤ 50, 1 ≤ a_1, a_2, a_3, a_4 ≤ 1000$）。概率 $p_i$ 可通过公式 $p_i = \frac{a_i}{a_1 + a_2 + a_3 + a_4}$ 计算。
## Output
可以证明，该问题的答案总是形如 $\frac{P}{Q}$ 的有理数，其中 $Q \not\equiv 0 \pmod{10^9 + 7}$。请输出 $P \cdot Q^{-1}$ 对 $10^9 + 7$ 取模的结果。
[samples]
## Note
在第一个示例中，芯片初始时位于与原点距离为 $0$ 的位置。一秒钟后，芯片会沿某个方向移动到距离为 $1$ 的位置，因此到原点的距离变为 $1$。第二个和第三个测试用例的答案分别为 $666666674$ 和 $538461545$。
**Definitions**
Let $ R \in \mathbb{Z}_{\geq 0} $ be the distance threshold.
Let $ a_1, a_2, a_3, a_4 \in \mathbb{Z}_{\geq 1} $ be integers defining transition probabilities.
Define probabilities:
$$
p_1 = \frac{a_1}{S}, \quad p_2 = \frac{a_2}{S}, \quad p_3 = \frac{a_3}{S}, \quad p_4 = \frac{a_4}{S}, \quad \text{where } S = a_1 + a_2 + a_3 + a_4.
$$
Let $ (X_t, Y_t) \in \mathbb{Z}^2 $ denote the position of the chip at time $ t \in \mathbb{Z}_{\geq 0} $, with $ (X_0, Y_0) = (0, 0) $.
The transition is:
$$
(X_{t+1}, Y_{t+1}) =
\begin{cases}
(X_t - 1, Y_t) & \text{w.p. } p_1, \\
(X_t, Y_t - 1) & \text{w.p. } p_2, \\
(X_t + 1, Y_t) & \text{w.p. } p_3, \\
(X_t, Y_t + 1) & \text{w.p. } p_4.
\end{cases}
$$
**Constraints**
1. $ 0 \leq R \leq 50 $
2. $ 1 \leq a_i \leq 1000 $ for $ i \in \{1,2,3,4\} $
3. The process stops at the first time $ \tau = \min \{ t \geq 1 : \sqrt{X_t^2 + Y_t^2} > R \} $
**Objective**
Compute the expected stopping time $ \mathbb{E}[\tau] $.
It is given that $ \mathbb{E}[\tau] = \frac{P}{Q} $ for coprime integers $ P, Q \in \mathbb{Z} $, $ Q \not\equiv 0 \pmod{10^9+7} $.
Output $ P \cdot Q^{-1} \mod (10^9 + 7) $, where $ Q^{-1} $ is the modular multiplicative inverse of $ Q $ modulo $ 10^9 + 7 $.
API Response (JSON)
{
"problem": {
"name": "E. Circles of Waiting",
"description": {
"content": "A chip was placed on a field with coordinate system onto point (0, 0). Every second the chip moves randomly. If the chip is currently at a point (_x_, _y_), after a second it moves to the point (_x_ ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF963E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "A chip was placed on a field with coordinate system onto point (0, 0).\n\nEvery second the chip moves randomly. If the chip is currently at a point (_x_, _y_), after a second it moves to the point (_x_ ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "一个芯片被放置在带有坐标系的场上的点 $(0, 0)$ 处。\n\n每秒，芯片随机移动。如果芯片当前位于点 $(x, y)$，则一秒钟后，它以概率 $p_1$ 移动到点 $(x - 1, y)$，以概率 $p_2$ 移动到点 $(x, y - 1)$，以概率 $p_3$ 移动到点 $(x + 1, y)$，以概率 $p_4$ 移动到点 $(x, y + 1)$。保证 $p_1 + p_2 + p_3 ...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ R \\in \\mathbb{Z}_{\\geq 0} $ be the distance threshold. \nLet $ a_1, a_2, a_3, a_4 \\in \\mathbb{Z}_{\\geq 1} $ be integers defining transition probabilities. \nDefine probabilitie...",
"is_translate": false,
"language": "Formal"
}
]
}