Задачі
Послідовність
Послідовність
Відома рекурентна формула для послідовності \textbf{f}:
\textbf{f(n) = 1 + f(1)g(1) + f(2)g(2) + ... + f(n-1)g(n-1)},
де \textbf{g} - також послідовність з наступною рекурентною формулою:
\textbf{g(n) = 1 + 2g(1) + 2g(2) + 2g(3) + ... + 2g(n-1) - g(n-1)g(n-1)}.
Крім того, відомо, що: \textbf{f(1) = 1}, \textbf{g(1) = 1}.
Ваша задача - знайти \textbf{f(n)} по модулю \textbf{p}.
\InputFile
У вхідному файлі міститься декілька тестів. Кожен тест у окремому рядку містить два числа: \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{10000}) та \textbf{p} (\textbf{2} ≤ \textbf{p} ≤ \textbf{2·10^9}). Тест з \textbf{n=p=0} завершує вхідний файл, він не повинен опрацьовуватись. Кількість тестів у одному файлі не перевищує \textbf{5000}.
\OutputFile
У вихідний файл для кожного тесту виведіть у окремому рядку єдине число - \textbf{f(n)} по модулю \textbf{p}.
Вхідні дані #1
1 2 2 11 0 0
Вихідні дані #1
1 2