← 返回题目列表

AtCoder · awc0048_e

E. 团队组建

中文机器翻译题面 查看原题

分数: 433 分

问题陈述

高桥正在为学校的文化节组织一场智力竞赛。有 N 参加知识竞赛的学生,以及学生 i (1 \leq i \leq N) 具有技能值 A_i。即使某些学生具有相同的技能值,每个学生也会被视为不同的人。

高桥将准确选择 K 这些人 N 学生组成一队。每个学生只能被选择一次。为了保证比赛的公平性,他希望所选选手的技能值相加 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
  • 第一行包含整数 N 代表学生人数,整数 K 代表要选择的人数,整数 M 这是多个条件的基础,用空格分隔。
  • 第二行包含整数 A_1, A_2, \ldots, A_N 代表每个学生的技能值,以空格分隔。

输出

在一行上打印精确选择的方法数量 K 人来自 N 学生的技能值之和是以下的倍数 M,模数 10^9 + 7.


示例输入 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