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