Hint

There was supposed to be a background story that fits the title, but since the author was too lazy, it was never written. We look forward to seeing it on the Lightnovel OJ in the future.

We call a $k$-permutation a permutation $p$ such that for all $1 \le i < n$, $|p_i - p_{i+1}| \neq k$.

Given positive integers $n$ and $M$, you will be asked $q$ queries. For each query, you are given a $k$, and you must answer how many permutations of order $n$ are $k$-permutations. Since the answer can be very large, output the result modulo $M$.

Input

The input is read from the file fate.in.

The first line contains three positive integers $n, q, M$, representing the order of the permutation, the number of queries, and the modulus, respectively.

The next $q$ lines each contain a positive integer $k$, representing the $k$ to be queried.

Output

The output is written to the file fate.out.

Output $q$ lines, each containing an integer representing the number of permutations modulo $M$.

Examples

Input 1

5 5 998244353
1
2
3
4
5

Output 1

14
28
48
72
120

Note 2~3

See fate/fate2~3.in and fate/fate2~3.ans in the contestant directory.

Subtasks

For 100% of the data, $1 \le k \le n \le 2,000$, $10^8 \le M \le 10^9$, and all input $k$ are distinct. For 99% of the data, $n \le 10^3$.