Для натурального \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 В единственную строку выходного файла выведите ответ на задачу.