有一个无限大的二维方格网格。网格上的坐标由一对整数 $(i, j)$ 表示。
Snuke 想要进行一次随机游走。他从 $(0, 0)$ 出发，共走 $N$ 步。当他位于 $(i, j)$ 时，下一步的位置将是 $(i-1, j)$、$(i, j-1)$、$(i, j+1)$ 和 $(i+1, j)$ 中的一个。每种可能性发生的概率均为 $\frac{1}{4}$。
设 $E$ 为随机游走过程中访问过的不同单元格数量的期望值。计算 $E \times 4^N$ 对 $M$ 取模的结果（该值保证为整数）。注意，$(0, 0)$ 始终被视为已访问。
输入格式
输入包含两个整数 $N$ 和 $M$ ($1 \le N \le 5000$, $10^9 \le M \le 2 \times 10^9$)。
输出格式
在一行中输出答案。
样例
样例输入 1
2 1000000007
样例输出 1
44
样例输入 2
2015 2000000000
样例输出 2
1892319232