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