题目背景

译自 XXIX Olimpiada Informatyczna – I etap Układanie kart。

题目描述

我们用以下方法将一个排列递增排序:

一次操作：记第一个数字为 $k$，在排列中找到 $k-1$（$k=1$ 则取 $n$），把 $k-1$ 拉到排列的第一个位置，中间的数字依次后移。

一次操作的价值：$k-1$（或 $n$）在原排列的位置（这个从 $0$ 开始标号）。

一个排列的价值：进行若干次操作直到排列有序，价值为每次操作的价值之和。

给你 $n,m$，求所有 $n!$ 个排列的价值之和，对 $m$ 取模。

输入格式

一行两个正整数，$n,m$。

输出格式

一行一个整数，答案对 $m$ 取模的结果。

2 100

1

3 100

15

10 1000

100

500 100000

60000

100000 1000

0

提示

对于所有数据，$2\leq n\leq 1000000$，$2\leq m\leq 10^9$。