CF1194F Crossword Expert

今天 Adilbek 要参加概率论考试。不幸的是，当 Adilbek 到达大学时，已经有很多学生排队等着参加同样的考试了。Adilbek 估计他需要在到达后等待 $T$ 秒才能开始考试。 幸运的是，Adilbek 可以不用复习那些无聊的定理和公式来打发时间。他的智能手机上有一个应用，里面有 $n$ 个日本填字游戏可以解答。Adilbek 决定按照应用中给出的顺序，依次解答所有填字游戏，不跳过任何一个。对于每个填字游戏，给定一个数字 $t_i$，表示一个普通填字游戏专家解答该题所需的时间（单位为秒）。 Adilbek 是一位真正的填字游戏专家，但有时候他在解题时运气不佳。因此，他解第 $i$ 个填字游戏所需的时间要么是 $t_i$ 秒，要么是 $t_i+1$ 秒，概率各为 $\frac{1}{2}$（即他有 $\frac{1}{2}$ 的概率正好用 $t_i$ 秒解完，有 $\frac{1}{2}$ 的概率需要多花一秒）。所有这些事件都是独立的。 在 $T$ 秒过去后（或者如果他在 $T$ 秒之前解完了最后一个填字游戏），Adilbek 会关闭应用（如果他恰好在第 $T$ 秒完成某个填字游戏，则该题算作解答完成；否则当前题目不算解答完成）。他觉得计算 $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 \times 10^5$，$1 \le T \le 2 \times 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)$ 的形式给出。

第一个样例的答案为 $\frac{14}{8}$。 第二个样例的答案为 $\frac{17}{8}$。 由 ChatGPT 4.1 翻译