Informatica Online Judge

  수학 공부 [0221 / 00DD]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 124   Total Tried : 402


The Champion of this Problem (C++) : gs15036 - 0ms / 148byte
My Best Submission (C++) : N/A

[]

Background

지구 밖 GSHS 행성에는 생명체가 살고 있다. GSHS의 위대한 지배자인 TshoT 또한 수학 공부의 중요성을 잘 알기 때문에, sutekine에게 경우의 수 단원의 곱의 원리를 가르치고 있다. sutekine는 지능이 매우 낮아 문제가 너무 어렵다고 생각하고 있다. sutekine가 불쌍하니까 우리가 도와주자. 문제의 내용은 독립적인 사건들이 N개 있을 때 총 경우의 수를 구하는 것이다. 단, 총 사건의 수가 M미만인 경우에는 쉬운 문제를 낸 TshoT가 괘씸하므로 +1한 값을 답인 것으로 알려준다.

Input

독립적인 사건의 수 N(1 ≤ N ≤ 100)과 M(1 ≤ M ≤2^50), N개의 사건 각각의 경우의 수 (0 ≤ 경우의 수 ≤ 2^50) 가 주어진다.

Output

답을 M으로 나눈 나머지를 출력한다.

IO Example

입력
5 123
1 2 3 4 5

출력
121


Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]