doju

doju enjoys adding new data to problems on an online judge. Watching someone fail because of the data doju added makes doju very happy.

The problem doju is preparing data for today has this input format.

The first line contains an integer $n$ ($1 \le n \le \mathit{maxn}$). The second line contains $n$ distinct integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le \mathit{maxa}$) in increasing order.

The correct solution first computes the greatest common divisor $g$ of $a_1, a_2, \dots, a_n$, then computes $x = a_n / g - n$. It prints odd when $x$ is odd and even when $x$ is even.

Two wrong ways of computing $x$ still get this problem right once in a while.

1. $x = a_n / g$
2. $x = a_n - n$

Both methods print the parity of the $x$ they computed. Count the data files that make both methods print an answer different from the correct one. Two data files are different when $n$ differs or the sequence differs.

Given $\mathit{maxn}$, $\mathit{maxa}$ and $q$, write a program that computes the number of data files that make both wrong methods fail, modulo $q$.

The first line contains $\mathit{maxn}$, $\mathit{maxa}$ and $q$, separated by spaces. ($1 \le \mathit{maxn} \le 30000$, $\mathit{maxn} \le \mathit{maxa} \le 10^9$, $10^4 \le q \le 10^5 + 129$)

Print the number of data files that make both wrong methods fail, modulo $q$.

For $\mathit{maxn} = 3$ and $\mathit{maxa} = 6$ there are four such data files: $n = 1$ with the sequence $2$, $n = 1$ with the sequence $4$, $n = 1$ with the sequence $6$, and $n = 3$ with the sequence $2, 4, 6$.