Послідовність#4957
Відома рекурентна формула для послідовності :
де - також послідовність з наступною рекурентною формулою:
Крім того, відомо, що: f(1) = 1, g(1) = 1.
Ваша задача - знайти по модулю .
У вхідному файлі міститься декілька тестів. Кожен тест у окремому рядку містить два числа: (1 \le n \le 10000) та (2 \le p \le 2 \cdot 10^9). Тест з n=p=0 завершує вхідний файл, він не повинен опрацьовуватись. Кількість тестів у одному файлі не перевищує .
У вихідний файл для кожного тесту виведіть у окремому рядку єдине число - по модулю .
Приклад 1