J - ランダムウォーク
解説
/
入力は以下の形式で標準入力から与えられる。
答えを一行に出力せよ。
実行時間制限: 4 sec / メモリ制限: 512 MB
Problem Statement
無限に広い二次元のマス目がある。このマス目の座標は二つの整数 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) は常に一回以上訪れたマス目に含まれるものとする。Constraints
- 1 \leq N \leq 5000
- 10^9 \leq M \leq 2 \times 10^9
Input Format
N M
Output Format
Sample Input 1
2 1000000007
Sample Output 1
44
Sample Input 2
2015 2000000000
Sample Output 2
1892319232