分数: 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