题目描述

给定 $n$ 个苹果，对于苹果 $i$，其甜度为 $c_i$，$c_i \geq -1$。假如 $c_i = -1$，代表苹果 $i$ 是坏的，否则它是好的。

现在要用 $n - 1$ 条线把这 $n$ 个苹果连成一个连通块，也就是一棵树，定义树上一个苹果是有用的，当且仅当它是一个好苹果，且至少与一个好苹果直接相连，一棵树的权值定义为树上的有用的苹果的甜度之和。

给定 $\text{limit}$，问有多少种不同的生成树，满足其权值小于等于 $\text{limit}$，答案对 $10 ^ 9 + 7$ 取模。两个生成树是不同的，当且仅当存在一条边 $(u, v)$，满足 $(u, v)$ 在一棵生成树中出现，在另外一棵中没有出现。

输入格式

第一行两个整数 $n, \text{limit}$。
第二行 $n$ 个整数，依次描述 $c_i$。

输出格式

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

4 5
1 2 -1 3

7

数据范围与提示

对于 $20\%$ 的数据，$n \leq 20$；
对于另外 $40\%$ 的数据，坏苹果的数量 $\leq 1$；
对于 $100\%$ 的数据，$ n \leq 40; -1 \leq c_i \leq 2.5 \times 10 ^ 7; 0 \leq \text{limit} \leq 10 ^ 9 $。