doju

doju는 온라인 저지 문제에 새 데이터를 추가하는 일을 즐긴다. 자기가 추가한 데이터 때문에 틀리는 사람을 보면 아주 기뻐한다.

오늘 doju가 데이터를 만들 문제의 입력 형식은 다음과 같다.

첫째 줄에 정수 $n$ ($1 \le n \le \mathit{maxn}$)이 주어진다. 둘째 줄에 서로 다른 정수 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le \mathit{maxa}$)이 오름차순으로 주어진다.

이 문제의 올바른 풀이는 먼저 $a_1, a_2, \dots, a_n$의 최대공약수 $g$를 구하고, $x = a_n / g - n$을 구한다. 그 다음 $x$가 홀수면 odd를, 짝수면 even을 출력한다.

그런데 $x$를 아래 두 가지 방법으로 잘못 구해도 이 문제를 간혹 맞을 수 있다.

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

두 방법 모두 잘못 구한 $x$의 홀짝을 그대로 출력한다. 세어야 하는 것은 두 방법이 모두 올바른 답과 다른 답을 출력하게 만드는 데이터의 개수다. $n$이 다르거나 수열이 다르면 서로 다른 데이터로 센다.

$\mathit{maxn}$, $\mathit{maxa}$, $q$가 주어졌을 때, 잘못 구한 두 방법을 모두 틀리게 만드는 데이터의 개수를 $q$로 나눈 나머지를 구하는 프로그램을 작성하시오.

첫째 줄에 $\mathit{maxn}$, $\mathit{maxa}$, $q$가 공백으로 구분되어 주어진다. ($1 \le \mathit{maxn} \le 30000$, $\mathit{maxn} \le \mathit{maxa} \le 10^9$, $10^4 \le q \le 10^5 + 129$)

첫째 줄에 잘못 구한 두 방법을 모두 틀리게 만드는 데이터의 개수를 $q$로 나눈 나머지를 출력한다.

$\mathit{maxn} = 3$, $\mathit{maxa} = 6$인 경우 조건을 만족하는 데이터는 네 가지다. $n = 1$이고 수열이 $2$인 데이터, $n = 1$이고 수열이 $4$인 데이터, $n = 1$이고 수열이 $6$인 데이터, $n = 3$이고 수열이 $2, 4, 6$인 데이터다.