题目描述

题目译自 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$ 的结果。

2 100

1

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

样例 2

见附加文件下 [ukl1.in](file:ukl1.in) 和 [ukl1.out](file:ukl1.out)。

该样例满足 $n=3, m=100$，答案是 $15$。

样例 3

见附加文件下 [ukl2.in](file:ukl2.in) 和 [ukl2.out](file:ukl2.out)。

该样例满足 $n=10, m=1000$，答案是 $100$。

样例 4

见附加文件下 [ukl3.in](file:ukl3.in) 和 [ukl3.out](file:ukl3.out)。

该样例满足 $n=500, m=10^5$，答案是 $60000$。

样例 5

见附加文件下 [ukl4.in](file:ukl4.in) 和 [ukl4.out](file:ukl4.out)。

该样例满足 $n=10^5, m=1000$，答案是 $0$。

数据范围与提示

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

子任务编号	附加限制	分值
$1$	$n \leq 10$	$10$
$2$	$n \leq 2000$	$60$
$3$	无附加限制	$30$