Для натурального \textbf{m} та простого \textbf{p} позначимо через \textbf{deg_p(m)} показник входження числа \textbf{p} в канонічний розклад числа \textbf{m} на прості множники. Вам задано натуральне число \textbf{n} та просте число \textbf{p}. Потрібно обчислити остачу числа \textbf{n!/p^\{degp(n!)\}} при діленні на \textbf{p^4}. Іншими словами \textbf{n!} ділять націло на \textbf{p} доки це можливо, і отримане число беруть за модулем \textbf{p^4}. Число \textbf{n} буде задане у \textbf{p}-ковому запису, тобто \textbf{n} = \textbf{d_\{L-1\}p^\{L-1\}} + \textbf{d_\{L-2\}p^\{L-2\}} + ... + \textbf{d_1 p} + \textbf{d_0}, де \textbf{d_\{L-1\}}, \textbf{d_\{L-2\}}, ..., \textbf{d_1}, \textbf{d_0} - деякі цілі невід'ємні числа, менші \textbf{p} (цифри числа \textbf{n} у \textbf{p}-ковому запису). \InputFile У першому рядку вхідного файлу задано просте число \textbf{p} (\textbf{3} < \textbf{p} < \textbf{55000}) та натуральне число \textbf{L} ≤ \textbf{500000} - довжина \textbf{p}-кового запису числа \textbf{n}. У другому рядку записано через пропуск числа \textbf{d_\{L-1\}}, \textbf{d_\{L-2\}}, ..., \textbf{d_1}, \textbf{d_0}, при цьому \textbf{d_\{L-1\}} > \textbf{0}. \OutputFile У єдиний рядок вихідного файлу виведіть відповідь до задачі.