오버플로우와 모듈러

정수 오버플로란 정수형 변수가 연산 중에 표현할 수 있는 범위를 벗어나 의도와 다른 값이 저장되는 현상이다. 변수의 타입과 함께 그 크기가 미리 정해지는 C, C++, Java와 같은 언어에서 종종 발생한다.

일반적인 4바이트 정수형이 표현할 수 있는 가장 큰 양의 정수는 $2^{31}-1 = 2147483647$이다. 그런데 4바이트 정수 변수에 담긴 $1000000$과 $1000000$을 곱하면 어떻게 될까? 정확한 곱은 $1000000 \times 1000000 = 1000000000000$이지만, 이 값은 이미 표현 범위를 벗어났으므로 원하는 결과가 나오지 않고 해당 타입이 표현 가능한 다른 값으로 바뀌어 저장된다.

이를 피하는 첫 번째 방법은 더 넓은 범위의 정수 타입을 쓰는 것이다. 예를 들어 C와 C++의 long long, Java의 long을 쓰면 $-2^{63}$부터 $2^{63}-1$까지의 정수를 표현할 수 있다. 또한 Python처럼 타입에 메모리 제한이 없어 오버플로를 신경 쓰지 않아도 되는 언어도 있다.

이 문제에서는 $N$개의 정수를 곱한다. 정수의 곱은 매우 빠르게 커지므로 일반적인 정수 변수로 표현할 수 있는 범위를 쉽게 넘어간다. 그래서 다음 합동식을 이용해 $N$개의 정수를 곱한 값을 $M$으로 나눈 나머지를 구하자.

$(A \times B) \bmod M = ((A \bmod M) \times (B \bmod M)) \bmod M$

$N$개의 정수와 $M$이 주어질 때, 모든 정수의 곱을 $M$으로 나눈 나머지를 구하는 프로그램을 작성하시오.

첫째 줄에 연산할 정수의 개수 $N$ ($1 \le N \le 100$)과 $M$ ($1 \le M \le 2147483647$)이 주어진다. 둘째 줄에 $N$개의 정수 $a_i$ ($1 \le a_i \le 2147483647$)가 공백으로 구분되어 한 줄로 주어진다.

$N$개의 정수의 곱을 $M$으로 나눈 나머지를 한 줄에 출력한다.