E - Team Formation Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 433 点

問題文

高橋君は学校の文化祭でクイズ大会を企画しています。クイズ大会に参加する生徒は全部で N 人おり、生徒 i（1 \leq i \leq N）には実力値 A_i が設定されています。実力値が同じ生徒がいる場合でも、各生徒は異なる人物として区別されます。

高橋君はこの N 人の中からちょうど K 人を選んで 1 つのチームを作ります。このとき、各生徒は 1 回しか選べません。公平な大会にするため、選んだ K 人の実力値の合計が M の倍数になるようにしたいと考えています。

条件を満たす選び方が何通りあるか、10^9 + 7 で割った余りを求めてください。

ここで、正の整数 X が M の倍数であるとは、ある正の整数 k が存在して X = kM となることをいいます。

制約

  • 1 \leq N \leq 30
  • 1 \leq K \leq N
  • 1 \leq M \leq 10^9
  • 1 \leq A_i \leq 10^9
  • 入力はすべて整数

入力

N K M
A_1 A_2 \ldots A_N
  • 1 行目には、生徒の人数を表す整数 N 、選ぶ人数を表す整数 K 、倍数の基準となる整数 M が、スペース区切りで与えられる。
  • 2 行目には、各生徒の実力値を表す整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。

出力

N 人の生徒からちょうど K 人を選んだとき、実力値の合計が M の倍数となる選び方の数を 10^9 + 7 で割った余りを 1 行で出力せよ。

入力例 1

4 2 3
1 2 3 4

出力例 1

2

入力例 2

6 3 5
1 2 3 4 5 6

出力例 2

4

入力例 3

10 5 7
1 2 3 4 5 6 7 8 9 10

出力例 3

36

Score : 433 pts

Problem Statement

Takahashi is organizing a quiz competition for his school's cultural festival. There are N students participating in the quiz competition, and student i (1 \leq i \leq N) has a skill value A_i. Even if some students have the same skill value, each student is distinguished as a different person.

Takahashi will select exactly K people from these N students to form one team. Each student can only be selected once. To make the competition fair, he wants the sum of the skill values of the selected K people to be a multiple of M.

Find the number of ways to select the students that satisfy the condition, modulo 10^9 + 7.

Here, a positive integer X is a multiple of M if there exists a positive integer k such that X = kM.

Constraints

  • 1 \leq N \leq 30
  • 1 \leq K \leq N
  • 1 \leq M \leq 10^9
  • 1 \leq A_i \leq 10^9
  • All inputs are integers

Input

N K M
A_1 A_2 \ldots A_N
  • The first line contains the integer N representing the number of students, the integer K representing the number of people to select, and the integer M which is the base for the multiple condition, separated by spaces.
  • The second line contains the integers A_1, A_2, \ldots, A_N representing the skill values of each student, separated by spaces.

Output

Print on one line the number of ways to select exactly K people from N students such that the sum of their skill values is a multiple of M, modulo 10^9 + 7.

Sample Input 1

4 2 3
1 2 3 4

Sample Output 1

2

Sample Input 2

6 3 5
1 2 3 4 5 6

Sample Output 2

4

Sample Input 3

10 5 7
1 2 3 4 5 6 7 8 9 10

Sample Output 3

36