Послідовність

Відома рекурентна формула для послідовності f:

f(n) = 1 + f(1)g(1) + f(2)g(2) + ... + f(n-1)g(n-1),

де g - також послідовність з наступною рекурентною формулою:

g(n) = 1 + 2g(1) + 2g(2) + 2g(3) + ... + 2g(n-1) - g(n-1)g(n-1).

Крім того, відомо, що: f(1) = 1, g(1) = 1.

Ваша задача - знайти f(n) по модулю p.

Вхідні дані

У вхідному файлі міститься декілька тестів. Кожен тест у окремому рядку містить два числа: n (1 ≤ n ≤ 10000) та p (2 ≤ p ≤ 2·10^9). Тест з n=p=0 завершує вхідний файл, він не повинен опрацьовуватись. Кількість тестів у одному файлі не перевищує 5000.

Вихідні дані

У вихідний файл для кожного тесту виведіть у окремому рядку єдине число - f(n) по модулю p.

Приклади