← 返回题目列表

AtCoder · nyc2015_10

J. 随机游走

中文机器翻译题面 查看原题

问题陈述

有一个无限宽的二维网格。这个正方形的坐标是两个整数 使用 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