今天阿迪贝克正在参加概率论考试。不幸的是,当阿迪贝克到达大学时,想要参加同样考试的学生已经排起了长队。 Adilbek估计他来后只需$$$T$$$秒就能开始测试。
幸运的是,Adilbek 可以花时间而不用修改任何无聊的定理或公式。他的智能手机上有一个应用程序,其中包含需要解决的 $$$n$$$ 日语填字游戏。阿迪贝克决定按照应用程序中列出的顺序一一解决所有问题,不跳过任何填字游戏。对于每个填字游戏,给出一个数字$$$t_i$$$,表示填字游戏专家解决该填字游戏的平均时间(时间以秒为单位)。
Adilbek 是一位真正的填字游戏专家,但不幸的是,他有时在选择解决填字游戏的方式时并不走运。因此,他需要花费 $$$t_i$$$ 秒或 $$$t_i + 1$$$ 秒来解开第 $$$i$$$ 个填字游戏(以 $$$\frac{1}{2}$$$ 的概率,他恰好在 $$$t_i$$$ 秒内解出填字游戏,并且以 $$$\frac{1}{2}$$$ 的概率,他必须额外花费一秒来完成填字游戏)。所有这些事件都是独立的。
经过 $$$T$$$ 秒后(或解决最后一个填字游戏后,如果他设法在不到 $$$T$$$ 秒内完成),Adilbek 会关闭应用程序(如果他同时完成一些填字游戏,则该填字游戏被视为已解决;否则 Adilbek 根本没有完成当前填字游戏的解决)。他认为计算 $$$E$$$(他能够完全解决的填字游戏的预期数量)将是一个有趣的概率论问题。你能计算一下吗?
回想一下,离散随机变量的期望值是所有可能值的概率加权平均值 - 在这个问题中,这意味着解决的填字游戏数量的期望值可以计算为 $$$E = \sum \limits_{i = 0}^{n} i p_i$$$,其中 $$$p_i$$$ 是 Adilbek 准确解决 $$$i$$$ 填字游戏的概率。
我们可以将 $$$E$$$ 表示为有理分数 $$$\frac{P}{Q}$$$,其中 $$$Q > 0$$$。要给出答案,您应该打印 $$$P \cdot Q^{-1} \bmod (10^9 + 7)$$$。
输入
第一行包含两个整数 $$$n$$$ 和 $$$T$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le T \le 2 \cdot 10^{14}$$$) — 分别是填字游戏的数量和 Adilbek 必须花费的时间。
第二行包含 $$$n$$$ 整数 $$$t_1, t_2, \dots, t_n$$$ ($$$1 \le t_i \le 10^9$$$),其中 $$$t_i$$$ 是填字游戏专家解决第 $$$i$$$ 个填字游戏所需的时间。
请注意,Adilbek 按照输入中给出的顺序解决填字游戏,而不会跳过任何一个。
输出
打印一个整数 — Adilbek 在 $$$T$$$ 秒内解决的填字游戏数量的预期值,以 $$$P \cdot Q^{-1} \bmod (10^9 + 7)$$$ 的形式表示。
示例
输入 #1
3 5 2 2 2
输出 #1
750000007
输入 #2
3 5 2 1 2
输出 #2
125000003
注意
第一个样本的答案等于 $$$\frac{14}{8}$$$。
第二个样本的答案等于 $$$\frac{17}{8}$$$。