Bajtazar likes playing bridge, but he finds it difficult to arrange cards in his hand efficiently. Therefore, before his next game with friends, he decided to practice sorting cards.

To do this, he prepared a special training deck of $n$ cards numbered from $1$ to $n$. He starts the exercise by shuffling the cards, which results in a certain permutation of cards in his hand. Then, he wants to arrange these cards in increasing order.

As long as the cards are not sorted, Bajtazar performs the following operation: he looks at the number of the first card in his hand (let's denote it by $k$) and finds the card with the number $k-1$ (unless $k=1$, in which case he finds the card with the number $n$), and then moves it to the beginning. The time taken for this operation is proportional to the distance of the found card from the beginning of the sequence of cards. The time to sort the cards is the sum of the times of all performed operations.

For example, the time to sort 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 \xrightarrow{5} 4\ 5\ 6\ 3\ 7\ 1\ 2 \xrightarrow{3} 3\ 4\ 5\ 6\ 7\ 1\ 2 \xrightarrow{6} 2\ 3\ 4\ 5\ 6\ 7\ 1 \xrightarrow{6} 1\ 2\ 3\ 4\ 5\ 6\ 7$.

Bajtazar would like to practice sorting for all $n!$ possible permutations. Write a program that will discourage him from this idea by calculating the total time required to perform this feat. For starters, it is enough if you determine the remainder of the division of the time by a given number $m$.

Input

The first and 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$).

Output

In the only line of output, print the total time to sort all permutations using Bajtazar's method modulo $m$.

Examples

Input 1

2 100

Output 1

1

Note 1

We have two permutations: $1\ 2$ (time $0$) and $2\ 1$ (time $1$).

Subtasks