נתונים מספר שלם חיובי $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$.