Factorial and fourth degree
For a natural number m and a prime number p let us denote by deg_p(m) the multiplicity of p in the canonical prime decomposition of m. You are given a natural number n and a prime number p. It is required to calculate a remainder of the division of n!/p^{degp(n!)} by p^4. In other words, we divide n! by p while it is possible, and yield obtained number modulo p^4. A number n is given in a base-p notation, i.e.
n = d_{L-1}p^{L-1} + d_{L-2}p^{L-2} + ... + d_1 p + d_0,
where d_{L-1}, d_{L-2}, ..., d_1, d_0 are some nonnegative integers less than p (digits of a number n in a base-p notation).
Input
The first line of the input file consists of a prime number p (3 < p < 55000) and a natural number L ≤ 500000, where L is length of a base-p notation of a number n. The second line consists of numbers d_{L-1}, d_{L-2}, ..., d_1, d_0, where d_{L-1} > 0.
Output
In the output file you should write the answer of the task.