打怪(monster) 1s 128MB O2 加速

题目描述

有n 个怪物,第i 个怪物的血量是a 。

现在你有一个技能,发动一次需要花费一个金币,当技能发动后,所有存活的怪物 的血量都会-1,当怪物血量降为0后视为被消灭。特别的,如果这次发动的技能后 有至少一只怪物死亡,你都将获得一个金币的奖励。

令f (s )为消灭集合s 中的怪物总共需要付出几个金币,即花费的金币数量减去 获得的奖励金币数量。求这n 个怪物的所有子集的f 值之和。

答案对109 + 7取模。如果余数小于0,输出加上109 + 7的结果。

输入格式

第一行一个正整数n 。

第二行n 个正整数a ,表示第i 个怪物的血量。

输出格式

输出一个非负整数,表示答案。

样例输入1

5

1 2 2 2 4

样例输出1

33

样例输入输出2

见下发文件。

数据规模

共 10 个测试点。

测试点1,2,3满足n <= 15。

测试点4,5,6满足n <= 100,1 <= a i <= 100。

对于所有数据,满足1 <= n <= 105, 1 <= a i <= 109。