New Modulo Operation with Factorial

In this problem, a new operation denoted by \(\oplus\) is defined as follows: for two numbers \(x\) and \(y\), when computing \(x \oplus y\), if \(x\) is not a multiple of \(y\), then \(x \oplus y\) equals the remainder when \(x\) is divided by \(y\). Otherwise, if \(x\) is a multiple of \(y\), we continuously divide \(x\) by \(y\) until the result is no longer divisible by \(y\); let the final result be \(x'\), and then \(x \oplus y = x' \mod y\>.

For example, with \(y = 5\):

• \(4 \oplus 5 = 4\) (since 4 is not a multiple of 5, we have \(4 \mod 5 = 4\))
• \(20 \oplus 5 = 4\) (since 20 is divisible by 5, we get \(20/5 = 4\), and then \(4 \mod 5 = 4\))
• \(100 \oplus 5 = 4\) (since \(100/5 = 20\) which is divisible by 5, then \(20/5 = 4\); hence, the result is \(4 \mod 5 = 4\))

You are given a prime number \(p\). Then, for multiple queries, each query provides an integer \(n\). Your task is to compute \(n! \oplus p\), where \(n!\) is the factorial of \(n\), i.e., the product of all positive integers less than or equal to \(n\).

Hint: Since for \(n \ge p\) the factorial \(n!\) contains \(p\) as a factor, you need to remove all factors of \(p\) from \(n!\) before taking the modulo \(p\). The exponent of \(p\) in \(n!\) is given by Legendre's formula \(v = \lfloor n/p \rfloor + \lfloor n/p^2 \rfloor + \cdots\), and you are required to compute \(\frac{n!}{p^v} \mod p\).

inputFormat

The first line contains two space-separated integers: a prime number \(p\) and an integer \(q\) representing the number of queries. The following \(q\) lines each contain a single integer \(n\).

outputFormat

For each query, output the value of \(n! \oplus p\) on a separate line.

sample

5 3
4
5
6

4
4
4