{"raw_statement":[{"iden":"statement","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)."},{"iden":"input","content":"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).\n\nProbabilities _p__i_ can be calculated using formula ."},{"iden":"output","content":"It can be shown that answer for this problem is always a rational number of form , where .\n\nPrint _P_·_Q_ - 1 modulo 109 + 7."},{"iden":"examples","content":"Input\n\n0 1 1 1 1\n\nOutput\n\n1\n\nInput\n\n1 1 1 1 1\n\nOutput\n\n666666674\n\nInput\n\n1 1 2 1 2\n\nOutput\n\n538461545"},{"iden":"note","content":"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.\n\nAnswers to the second and the third tests: and ."}],"translated_statement":[{"iden":"statement","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"},{"iden":"input","content":"第一行包含五个整数 $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}$ 计算。"},{"iden":"output","content":"可以证明，该问题的答案总是形如 $\\frac{P}{Q}$ 的有理数，其中 $Q \\not\\equiv 0 \\pmod{10^9 + 7}$。请输出 $P \\cdot Q^{-1}$ 对 $10^9 + 7$ 取模的结果。"},{"iden":"examples","content":"输入\n0 1 1 1 1\n输出\n1\n\n输入\n1 1 1 1 1\n输出\n666666674\n\n输入\n1 1 2 1 2\n输出\n538461545"},{"iden":"note","content":"在第一个示例中，芯片初始时位于与原点距离为 $0$ 的位置。一秒钟后，芯片会沿某个方向移动到距离为 $1$ 的位置，因此到原点的距离变为 $1$。第二个和第三个测试用例的答案分别为 $666666674$ 和 $538461545$。"}],"sample_group":[],"show_order":[],"formal_statement":"**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 $.","simple_statement":null,"has_page_source":false}