Migrated from Lutece 2810 又是生成树

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

给你 $n$ 个带权点，权值为 $c_i$ $(c_i \ge -1)$ ,在本题中，如果 $c_i=-1$ ,则该点被定义为无效点，否则该点为非无效点。

现在你要用 $n-1$ 条边把这 $n$ 个点连成一棵树，我们现在定义一个点为有效点，当且仅当它为非无效点，并且至少与一个非无效点直接相连，一棵树的权值定义为树上有效点的权值之和。

给定限制 $lim$ ,问有多少种不同的生成树，满足其权值小于等于 $lim$ ，答案对 $10^9+7$ 取模。

两个生成树是不同的，当且仅当存在一条边 $(u,v)$ ，满足 $(u,v)$ 在一棵生成树中出现，在另外一棵中没有出现。

Input

第一行两个整数 $n,lim$ 。 第二行 $n$ 个整数，依次描述 $c_i$ 。

Output

输出一行一个整数，代表生成树的数量。

Samples

4 5
1 2 -1 3

7

Constraints

$n \le 40 , -1 \le c_i \le 2.5 \times 10^7 , 0 \le lim \le 10^9$

Resources

2022 UESTC ICPC Training for String and Search Algorithm