网易游戏的最后一题

moonwith

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.

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

input	output
4 10	2

moonwith

是网易游戏的，题目没写清楚，抱歉，这题随便蒙的

moonwith

我承认网易很高端，这是俄罗斯的网站ACM网站上的题目，据说没有标准答案的

moonwith

自己翻译了下，这道题主要是取材太淫荡了
在中土世界（托尔金的虚幻世界）上，树人是与精灵族共同出现的种族。当雅凡娜（奥力的老婆）得知奥力创造了矮人后，她很担心矮人会过分砍伐树林，于是她恳请伊露维塔（托尔金认为的至高无上的神）创造了树人来保护树林。树人被誉为树林的永恒守护者，他们保护树林以防兽人，矮人和其他危险的侵扰。树人刚苏醒时能够感知这个世界，但是他们不会说话，直到精灵们教他们如何交流。
精灵们很耐心很聪明用了个很有效的办法教会树人他们的语言。他们先教会第一只树人两个单词——yes and no
。然后让这只树人分别选择一只年长的和一只年幼的树人，并把这些东西都教给他们。然后，让这两只被教的树人再继续接受精灵们的高等教育。
每只接受完精灵们高等教育的树人都必须再选择一只年长的和一只年幼的并且从为接受过教育的树人，并且把他们所知道的词汇都教给被选择的两只树人。然后，这两只被选择的树人同样接受精灵们的高等教育。这个高等教育必须坚守这样的规则：年幼的树人可以从高等教育里学到的词汇与自己本身的词汇量是一样多的，而年老的树人可以从高等教育里学到的词汇仅仅只有一个。在接受完高等教育，树人的词汇量将不会增长。
假设中土世界的树人无限大，请你计算有多少个树人懂得K个单词。

要求：
输入：
正整数K和P
输出：
因为知道K个单词的树人数量可能相当大，所以我们的输出应该是这个数值模P（就是求余）

moonwith

希望有达人给个效率高点的算法