当前没有测试数据。

装法的计数问题

题目描述

在一处考古现场，研究员要挑选遗物样本打包带走。背包容量为 $W$，有 $n$ 件遗物，每件有体积。每件遗物最多取一件。研究员想知道，有多少种不同的装法能使总占用体积不超过 $W$。两种装法被认为不同，当且仅当所选遗物集合不同。请输出方案数对 $10^9+7$ 取模的结果。

输入格式

第一行包含两个整数 $n,W$。

接下来 $n$ 行，每行包含一个整数，表示一件遗物的体积。

输出格式

输出一个整数，表示满足条件的装法数量对 $10^9+7$ 取模。

输入输出样例 #1

输入 #1

3 4
1
3
4

输出 #1

6

数据范围

对于 $100\%$ 的数据，$1 \le n \le 200$，$1 \le W \le 2000$，体积在 $[1,10^4]$。EOF