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

## Dmitry Gozman Contest 1. Petrozavodsk training camp. Winter 2007

Соревнование завершено

## G. 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
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1528. Sequence