2017 年国际怪物大会聚集了来自世界各地的 $n$ 只怪物。大会主席需要解决以下问题：如果第 $i$ 只怪物（$1 \le i \le n$）有 $k_i$ 根手指，编号从 $0$ 到 $k_i - 1$，那么他可以抬起其中的 $j$ 根手指（$0 \le j \le k_i$），并按以下方式获得一个特定的数字：如果抬起某根手指，则将 $2^{\text{手指编号}}$ 加到当前数字中。结果，第 $i$ 只怪物可以数出 $nr_i$ 个不同的数字。因此，要求的计算结果是 $nr_1 + nr_2 + \dots + nr_n$，对 $10^9+7$ 取模。
任务
计算要求的总和，对 $10^9+7$ 取模。
输入格式
第一行包含数字 $n$。 第二行包含 $n$ 个正整数 $k_1, k_2, \dots, k_n$，分别代表每只怪物的手指数量。
输出格式
输出包含一个正整数，即要求的总和，对 $10^9+7$ 取模。
数据范围
- $n \le 200,000$，$0 \le k_i \le 1,000,000,000$。
- 手指编号从 $0$ 开始。
子任务
| 子任务 | 分值 | 额外输入限制 |
|---|---|---|
| 1 | 40 | $n \le 1,000, k_i \le 10,000$ |
| 2 | 100 | $n \le 200,000, k_i \le 1,000,000,000$ |
样例
输入 1
2 3 7
输出 1
136
说明
第一只怪物可以获得 8 个数字： 0 - 没有抬起手指； 1 - 抬起的手指编号为 0； 2 - 抬起的手指编号为 1； 3 - 抬起的手指编号为 0 和 1； 4 - 抬起的手指编号为 2； 5 - 抬起的手指编号为 0 和 2； 6 - 抬起的手指编号为 1 和 2； 7 - 抬起的手指编号为 0、1 和 2。
第二只怪物可以获得 128 个数字。