Background

Translated from XXIX Olimpiada Informatyczna – Stage I Układanie kart。

Problem Description

We sort a permutation into increasing order using the following method.

One operation: Let the first number be $k$. Find $k-1$ in the permutation (if $k=1$, take $n$). Move $k-1$ to the first position of the permutation, and shift the numbers in between one position to the right.

Cost of one operation: the position of $k-1$ (or $n$) in the original permutation (indexed starting from $0$).

Cost of a permutation: perform several operations until the permutation is sorted. The cost is the sum of the costs of all operations.

Given $n,m$, find the sum of the costs over all $n!$ permutations, modulo $m$.

Input Format

One line with two positive integers, $n,m$.

Output Format

One line with one integer, the answer modulo $m$.

2 100

1

3 100

15

10 1000

100

500 100000

60000

100000 1000

0

Hint

For all testdata, $2\leq n\leq 1000000$，$2\leq m\leq 10^9$。

Translated by ChatGPT 5