#P1711. 2024.3.17-XHS-第三题-塔子哥的题解

2024.3.17-XHS-第三题-塔子哥的题解

题目描述

塔子哥在整理自己博客上发布的题解时，会发现，每过一段时间，都会随机有一个题解点赞数量加1(每个题解被点赞的概率是相同的)。

现在塔子哥想知道，当第一次出现所有题解点赞数量均为偶数时，所有题解的总赞数之和的期望是多少?

输入描述

第一行输入一个正整数nn，代表塔子哥发布的题解数量

第二行输入nn个非负整数aia_i代表当日每个题解的点赞数

1≤n≤1051≤ n ≤ 10^5

0≤ai≤1090 ≤ a_i ≤ 10^9

输出描述

输出期望对10^9+7取模后的值。

样例

输入

2
1 2

输出

6

说明

有1/2的概率总赞数为4，1/4的概率为6，1/8的概率为8...以此类推，最终答案收敛于6。

知识点:*****

查看知识点以及同类型题目

Statistics