U121088 [FJOI2020]异构序列码性态问题

给出 $1$ 个输入序列 $a$ ， $1$ 个输出序列 $b$ 和 $2$ 个栈 $s_1,s_2$ ，初始时 $a$ 为 $[1,2,...,n]$ ，其余均为空。其中要求 $s_1$ 从栈顶到栈底递增， $s_2$ 从栈顶到栈底递减。 对于 $a$ 中每一个元素，要求执行以下步骤：从 $a$ 的末尾进入 $s_1$ ，从 $s_1$ 进入 $s_2$，从 $s_2$ 进入 $b$ 的开头。 要求通过执行以上步骤，使 $a$ 中所有元素进入 $b$ 中。此时 $b$ 为 $1\sim n$ 的一种排列。求 $1\sim n$ 的所有排列中，不可能在 $b$ 中出现的排列数量。由于答案较大，输出答案模 $p$ 的值。

输入包含多组数据。 对于每组数据，输入 $1$ 行，包含 $2$ 个数 $n,p$ ，意义如题目描述所示。

对于每组数据，输出 $1$ 行，包含 $1$ 个数，表示 $1\sim n$ 的所有排列中，不可能在 $b$ 中出现的排列数量。

对于 $100\%$ 的数据，$n\leq 5×10^5+5$ 。