AT_nyc2015_10 ランダムウォーク

[problemUrl]: https://atcoder.jp/contests/NYC2015/tasks/nyc2015_10 入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ 答えを一行に出力せよ。 ``` 2 1000000007 ``` ``` 44 ``` ``` 2015 2000000000 ``` ``` 1892319232 ```

N/A

N/A

### Constraints 無限に広い二次元のマス目がある。このマス目の座標は二つの整数 $ i,\ j $ を用いて $ (i,\ j) $ と表せる。 すぬけ君は、$ (0,\ 0) $ から出発し、$ N $ 歩ランダムウォークを行う。$ (i,\ j) $ にいるとき、一歩進むとそれぞれ $ 1/4 $ ずつの確率で $ (i-1,\ j),\ (i,\ j-1),\ (i,\ j+1),\ (i+1,\ j) $ に進む。 すぬけ君が $ N $ 歩ランダムウォークを行ったとき、一回以上訪れたマス目の個数の期待値を $ E $ とする。$ E\ \times\ 4^N $ を $ M $ で割ったあまりを求めよ。 ただし、$ (0,\ 0) $ は常に一回以上訪れたマス目に含まれるものとする。 - - - - - - - $ 1\ \leq\ N\ \leq\ 5000 $ - $ 10^9\ \leq\ M\ \leq\ 2\ \times\ 10^9 $