ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1537. Энты

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Энты были созданы в Первоначальную эпоху вместе с другими обитателями Средиземья. Эльфийские легенды гласят, что когда Варда зажгла Звёзды и пробудились Эльфы, вместе с ними пробудились и Энты в Великих Лесах Арды. Они оказались хорошими пастухами деревьев и стражами Леса. Гнев их был страшен настолько, что они могли крошить камни и сталь своими руками. Энты были не только сильны и бессмертны, но ещё и очень добры и мудры. Они любили деревья и Эльфов и охраняли их от зла.
Когда Энты пришли в Арду, они ещё не умели говорить — этому искусству их обучали Эльфы, и Энтам это ужасно нравилось. Им доставляло удовольствие изучать разные языки, даже щебетание Людей.
Эльфы выработали хорошую технику обучения энтов своему языку. Первый энт, которого обучили эльфы, выучил всего два слова — «tancave» (да) и «la» (нет). Обученный энт выбрал одного старого и одного молодого энта, не умеющих говорить, и обучил их всем словам, которые знал сам. Затем обучение этих двух энтов продолжили сами эльфы. Каждый обучившийся у эльфов энт снова выбирал из неговорящих сородичей одного старого и одного молодого, обучал их всем словам, которые знал, передавал эльфам и так далее.
Выяснилось, что более молодые энты выучивали у эльфов ещё ровно столько же слов, сколько они узнали от обучавшего их энта. А вот более старые, уже склонные к одеревенению энты, пополняли свой запас всего лишь одним словом. После обучения у эльфов энты до конца света уже не могли выучить ни одного нового слова.
Общее число энтов в Средиземье больше, чем вы думаете. Интересно, а сколько из них знают ровно 150 квенийских слов? Похожую задачу вам предстоит решить.

Исходные данные

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

Результат

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

Пример

исходные данныерезультат
4 10
2
Автор задачи: Сергей Пупырев
Источник задачи: Восьмое открытое личное первенство УрГУ (3 марта 2007)