题目描述
训练计划表上有 种训练项目,第 种单项耗时 分钟,每种项目可以重复安排任意多次(也可以不安排)。你要安排若干项训练使总时长恰好为 分钟,与安排的先后顺序无关,只看每种项目的次数。求方案数对 +7 取模;无法恰好填满时输出 0。
输入格式
第一行两个整数 和 ,表示项目种数与目标总时长。接下来 行,每行一个整数 ,表示第 种项目的单项耗时。
输出格式
一行一个整数,表示恰好填满 分钟的方案数对 +7 取模的结果(无法填满即为 0)。
样例
输入
3 5 1 2 3
输出
5
数据范围
- 对于 30% 的数据: 5, 100(可爆搜每种安排几次)。
- 对于 60% 的数据: 30, 3000。
- 对于 100% 的数据: 100, ,1 ,。