Problem Description

On the $XY$ coordinate plane, there is one starting point and one goal point. The starting point is at $(0, 0)$, and the goal point is at $(X, Y)$.

You will move using a method called "jump". Each jump will result in one of the following four movements chosen randomly:

• Move $D$ units parallel to the $X$ axis.
• Move $-D$ units parallel to the $X$ axis.
• Move $D$ units parallel to the $Y$ axis.
• Move $-D$ units parallel to the $Y$ axis.

Each of these movements is chosen with exactly a $1/4$ probability.

You start at the starting point and want to reach the goal point exactly after $N$ jumps.

Output the probability of achieving your goal.

Input Format

The input is given from the standard input in the following format:

$N$ $D$ $X$ $Y$

• The first line contains the number of jumps, an integer $N$ $(1 ≦ N ≦ 1,000)$, and the distance of each jump, an integer $D$ $(1 ≦ D ≦ 10^9)$, separated by spaces.
• The second line contains the coordinates of the goal point, integers $X, Y$ $(-10^9 ≦ X, Y ≦ 10^9)$, separated by spaces.

Output Format

Output the probability that you can reach the goal point in one line. Ensure a newline at the end of the output.

The answer will be considered correct if the absolute or relative error is within $10^{-9}$.

Sample Input and Output

Sample Input #1

2 10000000
10000000 10000000

Sample Output #1

0.125

Sample Input #2

100 2
3 7

Sample Output #2

0.0

Sample Input #3

11 8562174
25686522 17124348

Sample Output #3

0.018174648284912

Notes/Hints

Partial Points

• Correctly solving all cases where $1 ≦ N ≦ 8$ will award 90 points.
• Correctly solving all cases where $1 ≦ N ≦ 30$ will award an additional 10 points.
• Correctly solving all cases will award a bonus point.

Sample Explanation 1

The probability of jumping from $(0, 0)$ to $(10000000, 10000000)$ in 2 jumps is $1/8$.

Sample Explanation 2

Since jumps of even distances cannot reach odd coordinates, the probability of reaching is $0$.

见题面 Input 部分

见题面 Output 部分