#P18042. Sum of max of iai

Sum of max of iai

Sum of max of iai

题目描述

给定正整数 NN 和质数 PP。对于 1,2,…,N1,2,\ldots,N 的一个排列 a=(a1,…,aN)a=(a_1,\ldots,a_N),定义

f(a)=max⁡1≤i≤N(i⋅ai).f(a)=\max_{1\le i\le N}(i\cdot a_i).

求所有 N!N! 个排列的得分之和,对 PP 取模。

输入格式

一行两个整数 N,PN,P。

1≤N≤1041\le N\le10^4,108≤P<10910^8\le P<10^9,保证 PP 是质数。

输出格式

输出所有排列的得分之和对 PP 取模的结果。

样例 1

输入:

10 100000007

输出:

77379290

样例 2

输入:

1000 998244353

输出:

168695631

样例 1 的模数是九位整数 108+710^8+7。全部排列的得分之和为 277379304277379304。