「POI 2021/2022 R1」Układanie kart

题目描述

题目译自 XXIX Olimpiada Informatyczna – I etap 「Układanie kart」

Bajtazar 喜欢玩桥牌，但是他不知道如何快速地整理在手上的牌。所以他决定在和朋友们玩下一局之前，先练习一下整理牌。

为此，他准备了一副特殊的训练牌，共有 $n$ 张牌，从 $1$ 到 $n$ 编号。他的练习从洗牌开始，他会给他手上的牌一个随机的排列。然后他想按照升序的顺序来排列这些牌。

在牌没有排序之前，Bajtazar 执行以下操作：他看着手上的第一张牌的编号（记为 $k$），然后在手上找到编号为 $k-1$ 的牌（除非 $k=1$，那么他就找到编号为 $n$ 的牌），然后把它放到牌的最前面。这个操作的时间为找到的牌距离牌的开头的距离。排序牌的时间是所有执行操作的时间的总和。

例如，将排列 $5\,6\,3\,7\,1\,4\,2$ 进行排序的时间是 $5+3+6+6=20$，因为连续的操作序列是：

$5\,6\,3\,7\,1\,\underline{4}\,2\,\xrightarrow{5} 4\,5\,6\,\underline{3}\,7\,1\,2 \xrightarrow{3} 3\,4\,5\,6\,7\,1\, \underline{2} \xrightarrow{6} 2\,3\,4\,5\,6\,7\,\underline{1} \xrightarrow{6} 1\,2\,3\,4\,5\,6\,7$

Bajtazar 想要练习所有 $n!$ 种可能的排列的排序。写一个程序计算出完成这个壮举所需要的总时间，让他放弃这个想法。你只需要计算出时间对给定的数 $m$ 取模的结果。

输入格式

输入一行，包含两个整数 $n, m$（$2 \leq n \leq 10^6, 2 \leq m \leq 10^9$）。

输出格式

输出一行一个整数，表示用 Bajtazar 的方法对所有排列进行排序的总时间模 $m$ 的结果。

样例 1

输入

2 100

输出

1

说明
我们有两种排列：$1\,2$（时间 $0$）和 $2\,1$（时间 $1$）。

数据范围与提示

详细子任务附加限制及分值如下表所示。