시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 7 4 3 60.000%

문제

doju의 취미는 BOJ 문제에 새로운 데이터를 추가하는 것이다. doju는 자신이 추가한 데이터로 인해 틀린 사람을 보면 매우 행복해한다.

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

첫째 줄에 정수 n (1 ≤ n ≤ maxn)이 주어진다. 둘째 줄에는 n개의 서로 다른 정수 a1, a2, ..., an (1 ≤ ai ≤ maxa)가 오름 차순으로 주어진다.

이 문제의 올바른 풀이는 먼저, a1, a2, ..., an의 최대공약수 g를 구하고 x = an/g - n을 구한다. 그 다음, x가 홀수면 "odd"를, 짝수면 "even"을 출력해야 한다.

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

  1. x = an/g
  2. x = an-n

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

입력

첫째 줄에 maxn, maxa, q가 주어진다. (1 ≤ maxn ≤ 30,000, maxn ≤ maxa ≤ 109, 104 ≤ q ≤ 105+129)

출력

첫째 줄에 문제에 주어진 두 방법을 모두 틀리게 만드는 데이터의 개수를 q로 나눈 나머지를 출력한다.

예제 입력 1

3 6 100000

예제 출력 1

4

예제 입력 2

6 21 100129

예제 출력 2

154

예제 입력 3

58 787788 50216

예제 출력 3

46009

힌트

첫 번째 예제의 경우 다음과 같은 4가지가 가능하다.

1
2
1
4
1
6
3
2 4 6

출처