问题陈述
有一个无限宽的二维网格。这个正方形的坐标是两个整数 使用 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
输入格式
N M
输出格式
示例输入 1
2 1000000007
示例输出 1
44
示例输入 2
2015 2000000000
示例输出 2
1892319232