Circles of Waiting

2000ms

262144K

Description:

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₁, to the point (x, y - 1) with probability p₂, to the point (x + 1, y) with probability p₃ and to the point (x, y + 1) with probability p₄. It's guaranteed that p₁ + p₂ + p₃ + p₄ = 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. $\text{[math]}$ will be satisfied).

Input:

First line contains five integers R, a₁, a₂, a₃ and a₄ (0 ≤ R ≤ 50, 1 ≤ a₁, a₂, a₃, a₄ ≤ 1000).

Probabilities p_i can be calculated using formula $\text{[math]}$ .

Output:

It can be shown that answer for this problem is always a rational number of form $\text{[math]}$ , where $\text{[math]}$ .

Print P·Q^- 1 modulo 10⁹ + 7.

Sample Input:

0 1 1 1 1

Sample Output:

Sample Input:

1 1 1 1 1

Sample Output:

666666674

Sample Input:

1 1 2 1 2

Sample Output:

538461545

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: $\text{[math]}$ and $\text{[math]}$ .

Informação

Provedor Codeforces

Código CF963E