题目描述

“连游走都不会，真菜。”

收到队友这样的评论后，新手小 C 开始游走了。地图可以看成一个平面直角坐标系，小 C 当前在 $(0,0)$。由于小 C 是新手，他每个时刻只会等概率地选择 $x$ 轴正方向、$x$ 轴负方向、$y$ 轴正方向、$y$ 轴负方向四个方向中的一个，向这个方向行进 $1$ 单位长度。例如第一个时刻过后，小 C 可能在 $(1,0),(-1,0),(0,1),(0,-1)$ 四个位置，概率都为 $\frac14$。

遇到小 C 这么菜的队友，你已经预见到 $n$ 个时刻后，你们会被击败。绝望的你打算计算出小 C 从 $(0,0)$ 开始，在 $n$ 个时刻内，走到的所有点到 $(0,0)$ 曼哈顿距离最大值的期望。

对于一个点 $(x,y)$，它到 $(0,0)$ 的曼哈顿距离为 $|x|+|y|$。由于答案的分子分母可能很大，请输出答案模给定质数 $p$ 意义下的值。

输入格式

第一行两个整数 $n,p$。

输出格式

一行一个整数表示答案。

样例输入

3 998244353

样例输出

811073539

样例解释

小 C 有 $64$ 种可能的行走方式，其中 $28$ 种行走方式经过的所有点到原点曼哈顿距离最大值为 $3$，$20$ 种为 $2$，$16$ 种为 $1$。

期望值为 $\frac{140}{64}\equiv 811073539\pmod{998244353}$。

数据范围

对于全部的数据，满足：

• $1\le n\le10^6$
• $10^8\le p\le10^9+7$
• $p$ 为质数