题目背景

每一次遗忘代表死亡

每一次彷徨后总失望

每一次白露沾染我裳

只得岁岁复常吟想

——MOCKER44. / 星尘《诗空茫》

题目描述

小 G 和小 L 在出模拟赛。

小 L 准备了 $n$ 道题，第 $i$ 题的难度为 $i$。他会将这些题给小 G，小 G 再从中选出三道题，不改变相对顺序地组成一场模拟赛。

由于操作失误，题目顺序被随机打乱了。小 L 想知道对于所有可能的排列，有多少种能从中选出一场难度递增的模拟赛。

形式化地，求有多少长为 $n$ 的排列满足其存在长为 $3$ 的上升子序列。由于答案可能很大，对给定模数 $m$ 取模后输出。

输入格式

一行两个整数 $n,m$，表示题目数量和模数。

输出格式

一行一个整数，表示合法排列数量对 $m$ 取模的结果。

输入 #1

3 998244353

输出 #1

1

输入 #2

19 998244353

输出 #2

99567690

输入 #3

499 998244353

输出 #3

337294617

输入 #4

4996 998244353

输出 #4

962884141

输入 #5

999325 123256072

输出 #5

32712512

说明/提示

样例 $1$ 解释：排列 $(1,2,3)$ 存在长为 $3$ 的上升子序列 $1,2,3$，其余排列均不存在长为 $3$ 的上升子序列，因此答案为 $1$。

对于所有数据，$3\le n\le 10^6,10^8\le m\le 10^9$。下表中留空代表无特殊限制。

\begin{array}{|c|c|c|} \hline \textbf{测试点} & n\le & m\\ \hline 1 & 10 & \textbf{}\\ \hline 2,3 & 20 & \textbf{}\\ \hline 4,5,6,7,8 & 500 & \textbf{}\\ \hline 9,10 & 5000 & =998244353\\ \hline 11,12,13,14,15,16 & 5000 & \textbf{}\\ \hline 17,18 & 10^6 & \textbf{为质数}\\ \hline 19,20 & 10^6 & \textbf{}\\ \hline \end{array}