给定 个苹果，对于苹果 ，其甜度为 ，。假如 ，代表苹果 是坏的，否则它是好的。

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

给定 ，问有多少种不同的生成树，满足其权值小于等于 ，答案对 取模。两个生成树是不同的，当且仅当存在一条边 ，满足 在一棵生成树中出现，在另外一棵中没有出现。