#P4312. [山东集训 2017] 苹果树

[山东集训 2017] 苹果树

题目描述

给定 nn 个苹果,对于苹果 ii,其甜度为 cic_ici1c_i \geq -1。假如 ci=1c_i = -1,代表苹果 ii 是坏的,否则它是好的。

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

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

输入格式

第一行两个整数 n,limitn, \text{limit}

第二行 nn 个整数,依次描述 cic_i

输出格式

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

4 5
1 2 -1 3
7

提示

对于 20%20\% 的数据,n20n \leq 20

对于另外 40%40\% 的数据,坏苹果的数量 1\leq 1

对于 100%100\% 的数据,$n \leq 40; -1 \leq c_i \leq 2.5 \times 10^7; 0 \leq \text{limit} \leq 10^9$。