Random Robot

Time limit1sMemory limit128 MB

Summary

Given move probabilities for E, W, S, N and up to 14 steps, compute the probability that the robot's random walk visits no grid cell twice.

Level: Medium6 of 10
Topics: Dynamic programming, Brute force, Probability
Solved: No attempts yet

Problem

A robot is on an infinite grid. It will make exactly N moves.

On each move, the robot chooses one of east, west, south, and north according to the given probabilities, then moves one cell in that direction.

A path is simple if no grid cell is visited more than once, including the starting cell. For example, EENE and ENW are simple paths, while ENWS and WWWWSNE are not because they visit a cell that was already visited. Here E, W, N, and S mean east, west, north, and south, respectively.

Compute the probability that the robot's path after N moves is simple.

Input

The first line contains N, followed by the probabilities of moving east, west, south, and north, in that order.

N is a positive integer no greater than 14. Each probability is an integer from 0 to 100, and the four probabilities sum to 100. Probabilities are given as percentages.

Output

Print the probability that the robot's path is simple.

An absolute or relative error of at most 10^-9 is accepted.

Examples5

Example 1
Input
```
2 25 25 25 25
```
Expected output
```
0.75
```
Example 2
Input
```
1 25 25 25 25
```
Expected output
```
1.0
```
Example 3
Input
```
7 50 0 0 50
```
Expected output
```
1.0
```
Example 4
Input
```
14 50 50 0 0
```
Expected output
```
0.0001220703125
```
Example 5
Input
```
14 25 25 25 25
```
Expected output
```
0.008845493197441101
```