{"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_ - 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.\n\nFind out the expected time after which chip will move away from origin at a distance greater than _R_ (i.e. will be satisfied).\n\n## Input\n\nFirst 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).\n\nProbabilities _p__i_ can be calculated using formula .\n\n## Output\n\nIt can be shown that answer for this problem is always a rational number of form , where .\n\nPrint _P_·_Q_ - 1 modulo 109 + 7.\n\n[samples]\n\n## Note\n\nIn 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.\n\nAnswers to the second and the third tests: and .","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 + p_4 = 1$。移动相互独立。\n\n求芯片移动到与原点距离大于 $R$ 所需的期望时间（即满足 $\\sqrt{x^2 + y^2} > R$）。\n\n第一行包含五个整数 $R, a_1, a_2, a_3$ 和 $a_4$（$0 ≤ R ≤ 50, 1 ≤ a_1, a_2, a_3, a_4 ≤ 1000$）。\n\n概率 $p_i$ 可通过公式 $p_i = \\frac{a_i}{a_1 + a_2 + a_3 + a_4}$ 计算。\n\n可以证明，该问题的答案总是形如 $\\frac{P}{Q}$ 的有理数，其中 $Q \\not\\equiv 0 \\pmod{10^9 + 7}$。\n\n请输出 $P \\cdot Q^{-1}$ 对 $10^9 + 7$ 取模的结果。\n\n在第一个示例中，芯片初始时位于与原点距离为 $0$ 的位置。一秒钟后，芯片会沿某个方向移动到距离为 $1$ 的位置，因此到原点的距离变为 $1$。\n\n第二个和第三个测试用例的答案分别为 $666666674$ 和 $538461545$。\n\n## Input\n\n第一行包含五个整数 $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}$ 计算。\n\n## Output\n\n可以证明，该问题的答案总是形如 $\\frac{P}{Q}$ 的有理数，其中 $Q \\not\\equiv 0 \\pmod{10^9 + 7}$。请输出 $P \\cdot Q^{-1}$ 对 $10^9 + 7$ 取模的结果。\n\n[samples]\n\n## Note\n\n在第一个示例中，芯片初始时位于与原点距离为 $0$ 的位置。一秒钟后，芯片会沿某个方向移动到距离为 $1$ 的位置，因此到原点的距离变为 $1$。第二个和第三个测试用例的答案分别为 $666666674$ 和 $538461545$。","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 probabilities:  \n$$\np_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.\n$$  \nLet $ (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) $.  \nThe transition is:  \n$$\n(X_{t+1}, Y_{t+1}) =\n\\begin{cases}\n(X_t - 1, Y_t) & \\text{w.p. } p_1, \\\\\n(X_t, Y_t - 1) & \\text{w.p. } p_2, \\\\\n(X_t + 1, Y_t) & \\text{w.p. } p_3, \\\\\n(X_t, Y_t + 1) & \\text{w.p. } p_4.\n\\end{cases}\n$$  \n\n**Constraints**  \n1. $ 0 \\leq R \\leq 50 $  \n2. $ 1 \\leq a_i \\leq 1000 $ for $ i \\in \\{1,2,3,4\\} $  \n3. The process stops at the first time $ \\tau = \\min \\{ t \\geq 1 : \\sqrt{X_t^2 + Y_t^2} > R \\} $  \n\n**Objective**  \nCompute the expected stopping time $ \\mathbb{E}[\\tau] $.  \n\nIt 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} $.  \nOutput $ P \\cdot Q^{-1} \\mod (10^9 + 7) $, where $ Q^{-1} $ is the modular multiplicative inverse of $ Q $ modulo $ 10^9 + 7 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF963E","tags":["math"],"sample_group":[["0 1 1 1 1","1"],["1 1 1 1 1","666666674"],["1 1 2 1 2","538461545"]],"created_at":"2026-03-03 11:00:39"}}