Problem1169--#6072. 「2017 山东一轮集训 Day5」苹果树

1169: #6072. 「2017 山东一轮集训 Day5」苹果树

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 512 MB

Description

给定 n n n 个苹果,对于苹果 i i i,其甜度为 ci c_i cici≥−1 c_i \geq -1 ci1。假如 ci=−1 c_i = -1 ci=1,代表苹果 i i i 是坏的,否则它是好的。

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

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

输入格式

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

输出格式

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

样例

样例输入

4 5
1 2 -1 3

样例输出

7

数据范围与提示

对于 20% 20\% 20% 的数据,n≤20 n \leq 20 n20
对于另外 40% 40\% 40% 的数据,坏苹果的数量 ≤1 \leq 1 1
对于 100% 100\% 100% 的数据,n≤40;−1≤ci≤2.5×107;0≤limit≤109 n \leq 40; -1 \leq c_i \leq 2.5 \times 10 ^ 7; 0 \leq \text{limit} \leq 10 ^ 9 n40;1ci2.5×107;0limit109

Source/Category