AT_nyc2015_10.ランダムウォーク

在一个无限大的二维网格上，每个格子的位置可以用两个整数坐标表示为 $(i, j)$。

Snuke 从起点 $(0, 0)$ 开始，他需要进行 $N$ 步的随机游走。在他每一步行走时，分别以 $\frac{1}{4}$ 的概率向四个方向移动，即 $(i-1, j), (i, j-1), (i, j+1), (i+1, j)$。

假设 Snuke 在完成 $N$ 步随机游走后，访问过的不同格子数的期望值是 $E$。我们要求出 $E \times 4^N$ 对 $M$ 取模的结果。需要注意的是，$(0, 0)$ 这个起始点总是被视为已访问的格子。

输入包含两行：

• 第一行：一个整数 $N$，表示行走的步数。
• 第二行：一个整数 $M$，需要用于取模。

输出一个整数，表示 $E \times 4^N$ 取模 $M$ 的结果。

• $1 \leq N \leq 5000$
• $10^9 \leq M \leq 2 \times 10^9$

本翻译由 AI 自动生成