背景

xtc Noip 完挂了,没有1=

描述

xtc由于Noip完挂了,他对H国产生了怨念,一怒之下决定破坏H国......
xtc有若干个核弹,决定投放在H国的水果生产地,H国的水果产地呈现出一个树形结构,并且每个水果产地都有一个生产力Vi。
xtc有一个投核弹的方案,方案中摧毁了若干个水果园,并且由于核辐射的缘故,如果一个产地只与被摧毁的产地相邻,那么它就会遭到强烈的核辐射,并且无法得到其他产地的援助而终止生产,其他的生产地不会受到影响。
由于xtc并不清楚H国的这个树形结构到底是怎样的,于是他决定问你,对于他的一个方案,有多少种可能的树形结构满足这个结构的最终生产力<=x

输入格式

第一行一个n,表示生产地个数
第二行有n个数,每个数都是一个正整数或者-1,正整数表示这个地方的生产力,-1表示这个地方已经被摧毁了。
第三行有一个整数x,意义如题面所述

输出格式

  一个整数,表示生产力小于等于x的生成树的个数Mod 10^9+7后的结果

样例输入

 4

  1 2 -1 3

  3

样例输出

 3

数据范围与约定

vi<=25000000
n<=40
x<=10^9
每个点时限4s

样例解释

来源

Topcoder