AdditionalFile5658.zip

#5658. 「POI2026 R3」Dyscyplina

标签: 传统 | 时间限制: 3000 ms | 内存限制: 128 MiB |

题目描述

题目译自 XXXIII Olimpiada Informatyczna – III etap Dyscyplina

在采石场工作是一项要求极高的差事。你不仅需要把石头从一个地方搬到另一个地方，还必须遵守采石场负责人的各种怪念头——据说这些规定是为了培养员工的纪律性。

采石场中有 $n$ 堆石头，编号从 $1$ 到 $n$。第 $i$ 堆由 $a_{i}$ 个石头组成。拜塔扎尔的任务是将所有的石头搬运到相邻的采石场。

由于这是一项劳累的工作，每天最多只能搬运一个石头。此外，根据负责人的构想，拜塔扎尔只有当数字 $k$ 的二进制表示中（从最低位起，编号当然是从 $1$ 开始）第 $i$ 位为 $1$ 时，才能在第 $k$ 天搬走第 $i$ 堆中的一个石头。例如，在第五天（二进制为 $101$），拜塔扎尔可以搬走第 $1$ 堆或第 $3$ 堆中的一个石头。

为了在遵守所有限制条件的前提下搬走采石场中所有的石头，至少需要经过多少天？由于这个数字可能非常大，请输出它对质数 $1000000007$ 取模后的结果。

输入格式

第一行包含一个正整数 $n$ $(1 \leq n \leq 10^{5})$，表示采石场中石堆的数量。

第二行包含 $n$ 个正整数 $a_{1}, a_{2}, \ldots, a_{n}$ $(1 \leq a_{i} \leq 10^{15})$，表示各石堆中的石头数量。

输出格式

你的程序应当输出搬走所有石头所需的最少天数对 $1000000007$ 取模的结果。

样例

输入

3
2 4 2

输出

9

达成结果为 $9$ 的一个示例方案是在各天依次从以下石堆搬走石头：$1, 2, 2, 3, 3, 2, 2, -, 1$。在第八天（用 $-$ 表示），我们选择不搬运任何石头。

附加样例

• $\texttt{0a}$：即为上述样例。
• $\texttt{0b}$：$n=4$，石堆中分别有 $1, 2, 3, 4$ 个石头。结果为 $11$。
• $\texttt{0c}$：$n=7$，所有的 $a_{i}$ 均为 $4$。结果为 $67$。
• $\texttt{0d}$：$n=8, a_{k}=a_{1}^{k} \pmod{10^{15}-11}$。结果为 $691312137$。

数据范围与提示

详细子任务附加限制及分值如下表所示。