One evening at the turn of the century, Dr. Ted Lewis, an astronomer living in a small town in the Mojave Desert, USA, was preparing a barbecue dinner for his wife's wedding anniversary when he suddenly discovered a huge meteor falling from the sky and crashing into a nearby hill. Ted went to investigate and discovered that the meteor was actually an alien flying saucer.

Ted decided to search for the elusive one-eyed alien monster Geta, but he still could not keep up with the monster's speed of devouring humans. Even more terrifying is that once the alien monster begins to multiply at a geometric rate, it will plunge the entire Earth into irreversible danger. The alien monster's cloning technique is a two-stage strategy measured in seconds. The first stage generates a cloning factor, and the second stage uses the generated cloning factor to replicate itself. At the 1st second after arriving on Earth, the cloning factor is 0, and at the 2nd second, the cloning factor is 1. Thereafter, the cloning factor $a_n$ at the $n$-th second is recursively generated as follows:

$$a_n = \frac{n a_{n-1} + (n-1) a_{n-2}}{2} + (-1)^n \left(1 - \frac{n}{2}\right), \quad n \ge 3$$

From the cloning factors generated in the first $n$ seconds, the alien monster can produce $s_n$ copies of itself at the $n$-th second as follows:

$$s_n = \sum_{i=1}^{n} \binom{n}{n-i} (n-i+1) a_i$$

where $\binom{n}{i}$ is the binomial coefficient, $\binom{n}{i} = \frac{n!}{i!(n-i)!}$.

To save the Earth, Ted needs to quickly calculate the alien monster's cloning speed so that he can manufacture enough extermination weapons.

Alien Flying Saucer Problem: For a given $n$, calculate the number of its own copies $s_n$ produced by the alien monster at the $n$-th second.

Input

There are several sets of test data. Each line provides a set of test data. Each set of test data consists of 2 non-negative integers $n$ and $q$. Here $n$ is the given number of seconds, and $q$ is a modulus.

Output

Output the calculated number of alien monster copies $(\text{mod } q)$.

Examples

Input 1

5 1283

Output 1

234

Input 2

75 1283

Output 2

980

Constraints

• For 30% of the test data, $n \le 230000, q \le 10^9 + 7$.
• For 80% of the test data, $n, q \le 10^9 + 7$.
• For 100% of the test data, $n \le 10^{19}, q \le 11223372019$.

Figure 1. An alien flying saucer