‹ 上一题 下一题 ›

j02056. 训练时长组合 未做

1000 ms 256 MB 测试点 10 背包问题J·复赛必做100题自拟题r2完全背包

题目描述

训练计划表上有 种训练项目,第 种单项耗时 分钟,每种项目可以重复安排任意多次(也可以不安排)。你要安排若干项训练使总时长恰好为 分钟,与安排的先后顺序无关,只看每种项目的次数。求方案数对 +7 取模;无法恰好填满时输出 0。

输入格式

第一行两个整数 和 ,表示项目种数与目标总时长。接下来 行,每行一个整数 ,表示第 种项目的单项耗时。

输出格式

一行一个整数,表示恰好填满 分钟的方案数对 +7 取模的结果(无法填满即为 0)。

样例

输入
3 5
1
2
3
输出
5

数据范围

  • 对于 30% 的数据: 5, 100(可爆搜每种安排几次)。
  • 对于 60% 的数据: 30, 3000。
  • 对于 100% 的数据: 100, ,1 ,。
输入
输出

            
答案