AT_abc011_4 [ABC011D] 大ジャンプ

[problemUrl]: https://atcoder.jp/contests/abc011/tasks/abc011_4 $ XY $ 座標上に、スタート地点とゴール地点が $ 1 $ つずつあります。 スタート地点は $ (0,\ 0) $ にあり、ゴール地点は $ (X,\ Y) $ です。 あなたは、ジャンプという移動法を用いて、移動を行います。 ジャンプを $ 1 $ 回行うと、あなたは、以下の $ 4 $ つのうち、ランダムで選ばれた $ 1 $ つの移動が行われます。 - $ X $ 軸に平行に $ +D $ だけ移動する。 - $ X $ 軸に平行に $ -D $ だけ移動する。 - $ Y $ 軸に平行に $ +D $ だけ移動する。 - $ Y $ 軸に平行に $ -D $ だけ移動する。 これらの移動は、どれもちょうど $ 1/4 $ の確率で選択されます。 あなたは、最初にスタート地点におり、ちょうど $ N $ 回のジャンプでゴール地点にたどり着きたいです。 目的を達成できる確率を出力しなさい。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ D $ $ X $ $ Y $ - $ 1 $ 行目には、ジャンプする回数を表す整数 $ N\ (1\ ≦\ N\ ≦\ 1,000) $ と、ジャンプの距離 $ D\ (1\ ≦\ D\ ≦\ 10^9) $ が、スペース区切りで与えられる。 - $ 2 $ 行目には、ゴール地点の座標を表す整数 $ X,\ Y\ (-10^9\ ≦\ X,\ Y\ ≦\ 10^9) $ が、スペース区切りで与えられる。

あなたが最終的にゴール地点にたどり着ける確率を $ 1 $ 行で出力せよ。出力の末尾にも改行をいれること。 なお、想定解答との絶対誤差または相対誤差が、$ 10^{-9} $ 以下であれば、正解として扱われる。

### 部分点 $ 1\ ≦\ N\ ≦\ 8 $ のケースに全て正解すると、部分点として $ 90 $ 点が与えられる。 $ 1\ ≦\ N\ ≦\ 30 $ のケースに全て正解すると、追加で $ 10 $ 点が与えられる。 全てのケースに正解すると、ボーナス点として $ 1 $ 点が与えられる。 ### Sample Explanation 1 $ (0,\ 0) $ から $ 2 $ 回のジャンプで $ (10000000,\ 10000000) $ へ飛ぶ確率は、 $ 1/8 $ です。 ### Sample Explanation 2 偶数の距離のジャンプでは、奇数の座標にたどり着くことはできないため、到達する確率は $ 0 $ となります。