카드 게임 대회

면접 대비

시간 제한1초메모리 제한256 MB

요약

N개의 게임 각각에 대해 Meiji는 A_i개의 덱을 가지고 있고, A_i가 0이면 기본 덱 하나를 받는다. 서로 다른 참가 방법의 수를 M으로 나눈 나머지를 구한다.

난이도: 쉬움10점 중 2점
유형: 수학, 구현, 조합론, 완전 탐색
정답자: 아직 제출이 없습니다

문제

메이지는 카드 게임 대회에 나가려고 한다. 대회에서는 $N$ 종류의 카드 게임이 열리고, 메이지는 그 $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$ 으로 나눈 나머지를 첫째 줄에 출력한다.

힌트

$N$ 이 0일 수 있다. $M$ 이 1이면 나머지는 항상 0이다.

예제3

예제 1
입력
```
3 99
4
3
0
```
예상 출력
```
12
```
예제 2
입력
```
3 10
4
3
0
```
예상 출력
```
2
```
예제 3
입력
```
0 10
```
예상 출력
```
1
```