TopCoder

Thumb mikasa mikoto furikae
Omelet
ㄏ一ㄏ一 $$AC \approx (111111111)_2$$

User's AC Ratio

100.0% (12/12)

Submission's AC Ratio

58.9% (33/56)

Tags

uva

Description

記得在快樂暑假營開始前,你曾經說過:「只要我有一次比賽沒有破台,就要請全快樂營的人吃布丁。」

好吧,蚯蚓太威了,你終究是沒有破台。

根據小道消息,你得知了這次的快樂暑假營總共有 n 個人報名,

但是實際上會出席的只有 k 個人,因此你只要請 k 個人吃布丁就好。

而報名的第 i 個人只會願意吃 t_i 口味的布丁(用一個 int 範圍內的整數表示)。

假設你不確定究竟誰會出席,那有幾種不同的布丁組合可能會出現在你的採買清單上 ?

喔對了,因為答案可能太大了,所以你決定只要知道答案除以 M 的餘數就好。

Input Format

輸入可能包含多筆測資,以 EOF 結束。

每筆測資的第一行有三個正整數,依序是 n、k、M (1≦n,k≦5,000 , 1≦M<231)。

接下來的一行有 n 個整數,第 i 個整數 t_i 代表第 i 個人願意吃的口味。

(測資間說不定會空一行。)

Output Format

對於每筆測資請輸出一行你覺得最有可能是答案的整數。

Sample Input

3 3 1
1 2 3

3 2 1000
1 2 2

4 3 1000
1 1 2 2

Sample Output

0
2
2

Hints

以第三筆範測為例,組合有 (1, 1, 2) (1, 2, 2) 兩種。

Problem Source

原TIOJ1628 / Adapted form UVa 10532
Problem Setter: suhorng

Subtasks

No. Testdata Range Score
1 0 20
2 1 20
3 2 20
4 3 20
5 4 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1500 65536 262144 1
1 1500 65536 262144 2
2 1500 65536 262144 3
3 1500 65536 262144 4
4 1500 65536 262144 5