g6-08001. 方案数·大 V 小和 未做

小杨在核对一批重物：有 $n$ 件物品，第 $i$ 件重量 $w_i$ 最多可达 $10^9$，每件只有一件，最多选一次。求选出物品总重量恰好等于 $V$（最多可达 $10^9$）的选法种数，答案对 $10^9+7$ 取模。数据保证所有 $w_i$ 之和小于 $V$。

第一行两个整数 $n,V$。

第二行 $n$ 个整数 $w_i$。

一行一个整数，方案数对 $10^9+7$ 取模。

输入 1

2 3000000000
1000000000 999999999

输出 1

0

所有重量和 $1999999999<V$，凑不出。

$1\le n\le 10^5$，$1\le V\le 10^9$，$1\le w_i\le 10^9$，保证 $\sum w_i<V$。