J - ランダムウォーク Editorial /

Time Limit: 4 sec / Memory Limit: 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