Migrated from Lutece 2785 啥b二次元 3

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

上回说到 Yo 和女朋友分手后全身心投入了二次元抽卡手游。 Yo 将他和女朋友的花销全部充到游戏里面，抽到了 $n$ 张卡，每张卡有个战力值，这 $n$ 张卡的战力为 $[1,n]$ 的排列。 由于 Yo 的不断反馈，策划修改了仓库里卡牌的排列规则，现在玩家可以自行排列卡牌。 但是由于原来的鬼畜排列，现在的 Yo 变得魔怔了，他将 $n$ 张卡牌依次排成一个序列，而且要求对于每张卡牌，相邻的卡牌战力值要么都比它大，要么都比他小（当然第 $1$ 和第 $n$ 张只有一个相邻卡牌）。 由于 Yo 和女朋友分手了所以现在有很多时间，所以 Yo 想知道总共有多少种排列方案。 由于 Yo 还要玩二次元游戏，所以他只想知道排列的方案数对 $mod$ 取模的结果。 由于 Yo 还要玩二次元游戏，所以他将这个问题交个你了。

两种排列不同当且仅当某个战力的卡牌所在位置不同。

Input

仅一行包含两个正整数 $n,mod$。

Output

一行一个整数表示答案

Samples

4 114514

10

5 1919810

32

Constraints

$3\le n\le 4500$ $2\le mod\le 10^9$

Resources

2022 UESTC ICPC Training for Dynamic Programming