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

1528. Sequence

Ограничение времени: 3.0 секунды
Ограничение памяти: 64 МБ
You are given a recurrent formula for a sequence f:
f(n) = 1 + f(1)g(1) + f(2)g(2) + … + f(n−1)g(n−1),
where g is also a recurrent sequence given by formula
g(n) = 1 + 2g(1) + 2g(2) + 2g(3) + … + 2g(n−1) − g(n−1)g(n−1).
It is known that f(1) = 1, g(1) = 1. Your task is to find f(n) mod p.

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

The input consists of several cases. Each case contains two numbers on a single line. These numbers are n (1 ≤ n ≤ 10000) and p (2 ≤ p ≤ 2·109). The input is terminated by the case with n = p = 0 which should not be processed. The number of cases in the input does not exceed 5000.

Результат

Output for each case the answer to the task on a separate line.

Пример

исходные данныерезультат
1 2
2 11
0 0
1
2
Автор задачи: Dmitry Gozman
Источник задачи: Dmitry Gozman Contest 1, Petrozavodsk training camp, January 2007