| ENG RUS | Timus 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.
Пример
Автор задачи: Dmitry Gozman Источник задачи: Dmitry Gozman Contest 1, Petrozavodsk training camp, January 2007 |