← 返回题目列表

Codeforces · 514/E

E. 达斯·维德和树

中文机器翻译题面 查看原题

当 Darth Vader 感到无聊时,他坐在沙发上,闭上眼睛,想象一棵无限根树,其中每个节点恰好有 n 个儿子,对于每个节点,它与其第 i 个左子节点之间的距离等于 di。西斯尊主喜欢计算树中距离根最多 x 的节点数。距离是节点之间路径上的边长度之和。

但他已经习惯了这种活动,甚至感到厌倦。 “那他为什么要这么做呢?” ——你可能会问。只是他知道只有他能解决这个问题而感到优越。

你想挑战达斯·维达本人吗?计算所需的节点数。由于答案可能相当大,请对 109 + 7 求模。

输入

第一行包含两个空格分隔的整数 n 和 x (1 ≤ n ≤ 105, 0 ≤ x ≤ 109) — 每个节点的子节点数量以及距离根的距离,在该范围内需要计算节点数。

下一行包含 n 个空格分隔的整数 di (1 ≤ di ≤ 100) — 连接每个节点与其第 i 个子节点的边的长度。

输出

打印单个数字 — 树中距根的距离最多等于 x 的顶点数。

示例

输入 #1

3 3
1 2 3

输出 #1

8

注意

到样本的图片(黄色标记距离最多为3的节点)