The University of the Minas Heptagon is creating a new operating system, "Janelas OS", which will come installed with the famous game Minesweeper. To avoid legal trouble, they decided to make 1-D Minesweeper, a version different enough to calm down the competitors' lawyers. The game works as follows:

• The minefield has $$$N$$$ positions, and each position may be empty or contain a mine.
• Each position may be revealed or secret – initially, all positions are secret.
• In each round, the player chooses a secret position and clicks it:
  • If the position contains a mine, the player loses.
  • If the position is empty, that position and all positions to the left and to the right of the click are revealed until the end of the field is reached or a mine is reached (that mine is also revealed).
• If at any moment all empty positions are revealed, the player wins. This may happen before the first click if there are no empty positions.

In the figure above, there are two example games for a given minefield. The one on the left ends in victory because all empty positions are found, and the one on the right ends in defeat because the player clicks a mine.

To help the university understand how long the game can entertain its users, given $$$N$$$, print how many different games can be played on a field of size $$$N$$$. Two games are considered different if the minefield is different, or if any move differs in order or position. Since the number of games can be very large, print the answer modulo $$$P$$$ – that is, the remainder of the division by $$$P$$$.