Энты были созданы в Первоначальную эпоху вместе с другими обитателями Средиземья. Эльфийские легенды гласят, что когда Варда зажгла Звёзды и пробудились Эльфы, вместе с ними пробудились и Энты в Великих Лесах Арды. Они оказались хорошими пастухами деревьев и стражами Леса. Гнев их был страшен настолько, что они могли крошить камни и сталь своими руками. Энты были не только сильны и бессмертны, но ещё и очень добры и мудры. Они любили деревья и Эльфов и охраняли их от зла.

Когда Энты пришли в Арду, они ещё не умели говорить — этому искусству их обучали Эльфы, и Энтам это ужасно нравилось. Им доставляло удовольствие изучать разные языки, даже щебетание Людей.

Эльфы выработали хорошую технику обучения энтов своему языку. Первый энт, которого обучили эльфы, выучил всего два слова — «tancave» (да) и «la» (нет). Обученный энт выбрал одного старого и одного молодого энта, не умеющих говорить, и обучил их всем словам, которые знал сам. Затем обучение этих двух энтов продолжили сами эльфы. Каждый обучившийся у эльфов энт снова выбирал из неговорящих сородичей одного старого и одного молодого, обучал их всем словам, которые знал, передавал эльфам и так далее.

Выяснилось, что более молодые энты выучивали у эльфов ещё ровно столько же слов, сколько они узнали от обучавшего их энта. А вот более старые, уже склонные к одеревенению энты, пополняли свой запас всего лишь одним словом. После обучения у эльфов энты до конца света уже не могли выучить ни одного нового слова.

Общее число энтов в Средиземье больше, чем вы думаете. Интересно, а сколько из них знают ровно 150 квенийских слов? Похожую задачу вам предстоит решить.

В единственной строке через пробел даны целые положительные числа K и P (K ≤ 10⁷; P ≤ 10⁹).

Мы понимаем, что число энтов, знающих в точности K слов, может быть слишком велико, поэтому просим вывести лишь количество энтов, знающих ровно K слов, по модулю P.