ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1537. Ents

Time limit: 1.0 second
Memory limit: 64 MB
Ents are a very old race that appeared in Middle-earth when the Elves did. They were apparently created by Eru Iluvatar at the behest of Yavanna after she learned of Aule's children, the Dwarves, knowing that they would want to fell trees. Ents were envisioned as immortal Shepherds of the Trees, to protect the forests from Orcs, Dwarves and other perils. Although the Ents were sentient beings at the time of their awakening, they did not know how to speak until the Elves taught them.
The Elves elaborated an effective technique of teaching Ents their language. The first Ent that was taught by the Elves learned two words only. They were «tancave» (yes) and «la» (no). Then this Ent chose one old Ent and one young Ent and taught them these words. After that these two Ents were taught further by the Elves. Then the process went as follows.
Each Ent who had finished his training with the Elves chose one old Ent and one young Ent that had not yet been taught and taught them all the words that he knew; after that these two Ents were trained further by the Elves. Each young Ent learned from the Elves as many new words as he had learned from the Ent who had taught him before. And each old Ent could enlarge his vocabulary with only one new word. After being trained by the Elves, Ents never learned any new words.
The total number of Ents in Middle-earth is greater than you think it is. Try to determine how many of them know exactly K words.

Input

The only input line contains positive integers K and P separated with a space. K ≤ 107, P ≤ 109.

Output

We understand that the number of Ents who know exactly K words can be too large, therefore we ask you to output this number modulo P.

Sample

inputoutput
4 10
2
Problem Author: Sergey Pupyrev
Problem Source: VIII USU Open Personal Contest (March 3, 2007)