시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB97438834141.283%

문제

메이지는 카드 게임 대회에 출전하려고 한다. 메이지는 $N$종류의 카드게임에 참가하려 한다. 어떤 카드 게임에 참가하기 위해서는, 그 게임에 맞는 카드 덱이 있어야 한다. 메이지는 $i$번째 게임에 대해, 메이지는 서로 다른 카드 덱을 $A_i$개 소유하고 있다. 만약, 참가자가 특정 게임에 대해 카드 덱이 없을 경우, 대회 주최측에서는 기본 카드덱을 준비 해 준다.

메이지는 자신이 얼마나 다양한 카드 덱 구성으로 참가할 수 있는지가 궁금해졌다. 서로 다른 방법으로 참여한다는 것은, 적어도 하나의 게임에 대해 다른 종류의 카드 덱으로 대회를 참가하는 것이다.

이때, 메이지가 서로 다른 방법으로 대회에 참여할 수 있는 방법의 수를 구하여라. 단, 답이 매우 클 수 있으니 답을 $M$으로 나눈 나머지를 출력하여라.

입력

첫째 줄에는, 정수 $N$, $M$이 공백으로 구분되어 들어온다. ($0 \le N \le 100$, $1 \le M \le 100$)

다음 $N$개의 줄의 $i$번째 줄에는, 정수 $A_i$가 들어온다. ($0 \le A_i \le 100$)

출력

메이지가 대회에 참여할 수 있는 방법의 수를 $M$으로 나눈 나머지를 구하여라.

예제 입력 1

3 99
4
3
0

예제 출력 1

12

예제 입력 2

3 10
4
3
0

예제 출력 2

2

예제 입력 3

0 10

예제 출력 3

1

힌트

$N$의 값이 0일 수 있음에 유의하여라.

출처

University > KAIST > 2017 KAIST RUN Spring Contest (HYEA Cup) A번