Migrated from Lutece 2676 行于边界的拉格兰 1

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

场景不停转换。

每踏出一步，四周的景象就会随之改变。她的脚步改变了脚下的地面，也改造了空间。 她走近织锦边，却发现布料不曾完整缝合。玻璃静静地滑过她的身边，然后突然四散，像是受到了惊吓。 她周遭的世界已变得漆黑而不再洁白。繁星洒落在空中，脚下的路却是如此支离破碎……

Arcaea 是一个由记忆编织而成的织锦。它也会在边角出现磨损，尽管那总是被忽略和遗忘。 站在那之前的少女，是第一个目睹此景之人。

拉格兰（Lagrange）行走在 Arcaea 世界的边角处，这里的世界变化无常，很难有正常的方向感。

我们假设拉格兰所行走的环境是一个二维网格平面。当拉格兰处于位置 $(x,y)$ 时，每一次行动后，她会以相同的概率前进到 $(x,y+1)$ 、 $(x,y-1)$ 、$(x+1,y)$ 、 $(x-1,y)$ 中的一个位置。

假设拉格兰从 $(0,0)$ 这个位置出发，问行动 $n$ 次后回到 $(0,0)$ 点的方案数有多少种？

两种行动方案相同当且仅当在两个方案中任意一次行动后所到达的位置都相同。

由于方案数可能有很多，你需要将答案对 $p$ 取模。（不保证 $p$ 是素数）

Input

第一行两个整数 $n,p$ ，$n$ 为行动的次数， $p$ 为答案所需取的模数。

Output

仅输出一个整数，代表方案数对 $p$ 取模的结果。

Samples

1 100

0

2 100

4

3 100

0

Constraints

$1 \le n \le 10^{12}$ $2 \le p \le 10^6$ ，不保证 $p$ 为素数。

Resources

2021 UESTC ICPC Training for Math and Geometry