Сізге оң бүтін $N$ саны және жай $P$ саны берілген.
$1, 2, \cdots, N$ сандарының $(a_1, a_2, \cdots, a_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$ бүтін саны екеніне назар аударыңыз.