Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. New Year and Permutation

time limit per test

1 secondmemory limit per test

1024 megabytesinput

standard inputoutput

standard outputRecall that the permutation is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array) and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

A sequence $$$a$$$ is a subsegment of a sequence $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. We will denote the subsegments as $$$[l, r]$$$, where $$$l, r$$$ are two integers with $$$1 \le l \le r \le n$$$. This indicates the subsegment where $$$l-1$$$ elements from the beginning and $$$n-r$$$ elements from the end are deleted from the sequence.

For a permutation $$$p_1, p_2, \ldots, p_n$$$, we define a framed segment as a subsegment $$$[l,r]$$$ where $$$\max\{p_l, p_{l+1}, \dots, p_r\} - \min\{p_l, p_{l+1}, \dots, p_r\} = r - l$$$. For example, for the permutation $$$(6, 7, 1, 8, 5, 3, 2, 4)$$$ some of its framed segments are: $$$[1, 2], [5, 8], [6, 7], [3, 3], [8, 8]$$$. In particular, a subsegment $$$[i,i]$$$ is always a framed segments for any $$$i$$$ between $$$1$$$ and $$$n$$$, inclusive.

We define the happiness of a permutation $$$p$$$ as the number of pairs $$$(l, r)$$$ such that $$$1 \le l \le r \le n$$$, and $$$[l, r]$$$ is a framed segment. For example, the permutation $$$[3, 1, 2]$$$ has happiness $$$5$$$: all segments except $$$[1, 2]$$$ are framed segments.

Given integers $$$n$$$ and $$$m$$$, Jongwon wants to compute the sum of happiness for all permutations of length $$$n$$$, modulo the prime number $$$m$$$. Note that there exist $$$n!$$$ (factorial of $$$n$$$) different permutations of length $$$n$$$.

Input

The only line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 250\,000$$$, $$$10^8 \le m \le 10^9$$$, $$$m$$$ is prime).

Output

Print $$$r$$$ ($$$0 \le r < m$$$), the sum of happiness for all permutations of length $$$n$$$, modulo a prime number $$$m$$$.

Examples

Input

1 993244853

Output

1

Input

2 993244853

Output

6

Input

3 993244853

Output

32

Input

2019 993244853

Output

923958830

Input

2020 437122297

Output

265955509

Note

For sample input $$$n=3$$$, let's consider all permutations of length $$$3$$$:

- $$$[1, 2, 3]$$$, all subsegments are framed segment. Happiness is $$$6$$$.
- $$$[1, 3, 2]$$$, all subsegments except $$$[1, 2]$$$ are framed segment. Happiness is $$$5$$$.
- $$$[2, 1, 3]$$$, all subsegments except $$$[2, 3]$$$ are framed segment. Happiness is $$$5$$$.
- $$$[2, 3, 1]$$$, all subsegments except $$$[2, 3]$$$ are framed segment. Happiness is $$$5$$$.
- $$$[3, 1, 2]$$$, all subsegments except $$$[1, 2]$$$ are framed segment. Happiness is $$$5$$$.
- $$$[3, 2, 1]$$$, all subsegments are framed segment. Happiness is $$$6$$$.

Thus, the sum of happiness is $$$6+5+5+5+5+6 = 32$$$.

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/22/2020 06:22:59 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|