当 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的节点)