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.