ROOBOT - Robot


There is a robot on the 2D plane. Robot initially standing on the position (0, 0). Robot can make a 4 different moves:

  1. Up (from (x, y) to (x, y + 1)) with probability U.
  2. Right (from (x, y) to (x + 1, y)) with probability R.
  3. Down (from (x, y) to (x, y - 1)) with probability D.
  4. Left (from (x, y) to (x - 1, y)) with probability L.

After moving N times Robot gets points.

  • Let x1 be the smallest coordinate in X-axis, that Robot reached in some moment.
  • Let x2 be the largest coordinate in X-axis, that Robot reached in some moment.
  • Let y1 be the smallest coordinate in Y-axis, that Robot reached in some moment.
  • Let y2 be the largest coordinate in Y-axis, that Robot reached in some moment.

Points achieved by Robot equals to x2 - x1 + y2 - y1.

Given N, U, R, D, L. Calculate expected value of points that Robot achieved after N moves.

Input

First line: One interger N (1 ≤ N ≤ 200).

Second line: Four real numbers U, R, D, L (U + R + D + L = 1, 0 ≤ U, R, D, L ≤ 1) with maximum of 6 numbers after dot.

Output

One number: expected value of points achieved by Robot. The answer will be considered correct if its relative or absolute error does not exceed 10-6.

Example 1

Input:
2
0.100000 0.200000 0.300000 0.400000

Output:
1.780000

Example 2

Input:
3
0.25 0.25 0.25 0.25

Output:
2.375000

hide comments
Luka �e�erovi�: 2016-04-04 16:30:53

Please give us more test cases! Thanks in advance :)

Scape: 2015-09-08 22:00:46

Any tricky test cases? Getting wrong answer even with long doubles.
UPD: There was a problem in judge. It's fixed now after I notified the setter. Thanks Bartek :)

Last edit: 2015-10-03 17:51:57
Sourav Kumar: 2015-09-02 21:33:09

Could someone give a few more test cases?


Added by:Bartek
Date:2015-08-30
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY