Sorting Cards

Bajtazar enjoys playing bridge, but he struggles to arrange his cards quickly in hand. Before his next game with friends, he wants to practice arranging cards.

He prepared a training deck of $n$ cards numbered from 1 to $n$. Each practice starts by shuffling the cards, which gives a permutation of the cards in hand. Then he wants to sort the cards in increasing order of their numbers.

While the cards are not sorted, Bajtazar repeats the following operation. He looks at the number of the first card in hand, call it $k$, and finds the card numbered $k-1$ in hand (if $k = 1$, he finds the card numbered $n$ instead). He then moves that card to the front. The time of this operation is proportional to the distance of the found card from the front of the sequence. The sorting time is the sum of the times of all operations performed.

For example, the sorting time of the permutation 5 6 3 7 1 4 2 is $5 + 3 + 6 + 6 = 20$, because the sequence of operations is:

5 6 3 7 1 4 2 → 4 5 6 3 7 1 2 → 3 4 5 6 7 1 2 → 2 3 4 5 6 7 1 → 1 2 3 4 5 6 7.

Bajtazar wants to practice sorting for all $n!$ possible permutations. Write a program that calculates the total sorting time over all these permutations, which discourages him from this idea. For now, it is enough to compute the remainder of this total time modulo $m$.

The only line of input contains two integers $n$ and $m$ ($2 \le n \le 1\,000\,000$, $2 \le m \le 1\,000\,000\,000$).

Print one line containing the total sorting time over all $n!$ permutations, modulo $m$.