กำหนดจำนวนเต็มบวก $N$ และจำนวนเฉพาะ $P$ มาให้
สำหรับการเรียงสับเปลี่ยน $(a_1, a_2, \cdots, a_N)$ ของ $1, 2, \cdots, N$ นิยามคะแนน $f(a)$ ของมันดังต่อไปนี้
$$f(a) = \max\{ia_i \mid i = 1, 2, \cdots, N\}$$
จงหาเศษเหลือเมื่อนำผลรวมของคะแนนของการเรียงสับเปลี่ยนทั้งหมดมาหารด้วย $P$
ข้อมูลนำเข้า
บรรทัดแรกประกอบด้วย $N, P$ ตามลำดับ คั่นด้วยช่องว่าง ($1 \le N \le 10^4$, $10^8 \le P < 10^9$, $P$ เป็นจำนวนเฉพาะ)
ข้อมูลส่งออก
พิมพ์เศษเหลือเมื่อนำผลรวมของคะแนนของการเรียงสับเปลี่ยนทั้งหมดมาหารด้วย $P$
ตัวอย่าง
ข้อมูลนำเข้าตัวอย่างที่ 1
10 100000007
ข้อมูลส่งออกตัวอย่างที่ 1
77379290
ข้อมูลนำเข้าตัวอย่างที่ 2
1000 998244353
ข้อมูลส่งออกตัวอย่างที่ 2
168695631
หมายเหตุ
สำหรับตัวอย่างแรก ตัวอย่างเช่น $f(3, 9, 4, 10, 8, 2, 7, 5, 6, 1) = 54$
ผลรวมของคะแนนของการเรียงสับเปลี่ยนทั้งหมด $10!$ แบบคือ $277379304$ และเศษเหลือเมื่อนำค่านี้ไปหารด้วยจำนวนเฉพาะ $P = 10^8 + 7$ คือ $77379290$ ดังนั้นจึงพิมพ์ $77379290$ โปรดสังเกตว่าสำหรับข้อมูลนำเข้าชุดนี้ จำนวนเฉพาะ $P$ คือจำนวนเต็ม $9$ หลัก $10^8 + 7$