Известна рекуррентная формула для последовательности \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}.