Finally, Rikka got an excellent design which not only creates efficient traffic but also costs little money. But Rikka didn't care whether the trite officers accepted it — LCR had been behind her for long, with a chaste smile, a garland, and a white dress. Gradually calmed down by the smile, the girls reached out their hands and began their journey. They ended up at a self-study room in the Middle School Attached to Northwestern Polytechnical University after the romantic meeting.

The formulas on the whiteboards and papers have reminded Rikka (about her study, of course), so she is asking LCR to play a game with her now (in order to review combinatorics).

LCR has an $$$n$$$-order permutation and Rikka tries to guess it. At first, Rikka should choose a set of $$$n$$$-order permutations. LCR will make some queries then. Each time, LCR gives a segment $$$[L, R]~(1\le L\le R\le n)$$$ and for each chosen permutation Rikka answers if the segment is consecutive (defined in the following paragraphs) in it. In the end, Rikka will win the game if and only if there exists a chosen permutation which has the same answer to each query as LCR's original one.

Rikka wonders how many permutations she has to choose at least to ensure winning the game. For future games, she needs the answer for each positive integer $$$n$$$ not greater than $$$N$$$. She only needs the answer modulo a certain prime $$$P$$$ because its exact value may be too large.

The segment $$$[L, R]$$$ is consecutive in an $$$n$$$-order permutation $$$p$$$ if and only if there doesn't exist three integers $$$x, y, z$$$ such that $$$1\le x, y, z\le n$$$, $$$p_x<p_y<p_z$$$, $$$x, z \in [L, R]$$$, $$$y \notin [L, R]$$$, where $$$p_i~(i = 1, 2, \dots, n)$$$ is an integer in $$$[1, n]$$$, which means the $$$i$$$-th element in the permutation $$$p$$$.