#P9102. [PA2020] Cukierki

[PA2020] Cukierki

题目描述

题目译自 PA 2020 Runda 5 Cukierki

Bytie 要去参加 Bitek 的生日聚会。他知道 Bitek 喜欢吃甜食,所以他想送他一些糖果作为礼物。他买了 nn 袋糖,其中第 ii 袋包含 aia_i 个糖果。

然而,这些糖相当重,Bytie 想知道他是否需要把它们全都给 Bitek。他决定,他将选择一个非空的袋装糖果子集,把它们拿给 Bitek,并对他说:「我这里总共有 xx 颗糖果,你想要多少?」,其中 xx 将是带到派对上的包装里的糖果总数。Bitek 听到这个问题后,可能会选择区间 [1,x][1, x] 中的任何整数 yy。无论 Bitek 的回答如何,他都希望能够从带到派对上的糖中选择一部分(其余的留给自己),这样这些袋糖中的糖果总数正好等于 yy。当然,不可以撕毁包装纸——给散装的糖果是不礼貌的。

因此,Bytie 在想,他能给 Bitek 带去多少种非空的袋装糖果子集,以便在不考虑 Bitek 的选择的情况下,能够送给他所需数量的糖果。请帮助他计算一下吧!由于这种子集的数量可能非常大,请输出它对 109+710^9+7 取模后的结果。

输入格式

第一行一个整数 nn,表示 Bytie 有的袋装糖果数量。

第二行 nn 个整数 a1,a2,,ana_1,a_2,\cdots,a_n,表示每袋糖果中糖果的数量。

输出格式

输出可能的袋装糖果子集种类数对 109+710^9+7 取模后的值。

5
2 7 4 4 1
8

提示

样例 1 解释

Bytie 可以带去 88 种非空子集:$\{5\}, \{1, 5\}, \{1, 3, 5\}, \{1, 4, 5\}, \{1, 3, 4, 5\}, \{1, 2, 3, 5\}, \{1, 2, 4, 5\}$ 和 {1,2,3,4,5}\{1, 2, 3, 4, 5\}。例如,Bytie 带去的子集是 {1,2,4,5}\{1,2,4,5\},Bitek 想要 99 颗糖果时,Bytie 只能给他第 1,21,2 包糖。Bytie 不可以带去 {1,2,5}\{1,2,5\} 子集,如果 Bitek 想要 66 颗糖的话 Bytie 就犯难了。


数据范围

本题采用捆绑测试

对于 100%100\% 的数据,保证 1n5×1031\le n\le 5\times 10^31ai5×1031\le a_i\le 5\times 10^3