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

USU Open Personal Contest 2007

About     Problems     Submit solution     Judge status     Standings
Contest is over

F. 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.


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


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.


4 10
Problem Author: Sergey Pupyrev
Problem Source: VIII USU Open Personal Contest (March 3, 2007)
To submit the solution for this problem go to the Problem set: 1537. Ents