题目描述

题目译自 PA 2020 Runda 5 Cukierki

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

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

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

输入格式

第一行一个整数 $n$，表示 Bytie 有的袋装糖果数量。

第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$，表示每袋糖果中糖果的数量。

输出格式

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

5
2 7 4 4 1

8

提示

样例 1 解释

Bytie 可以带去 $8$ 种非空子集：$\{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\}$。例如，Bytie 带去的子集是 $\{1,2,4,5\}$，Bitek 想要 $9$ 颗糖果时，Bytie 只能给他第 $1,2$ 包糖。Bytie 不可以带去 $\{1,2,5\}$ 子集，如果 Bitek 想要 $6$ 颗糖的话 Bytie 就犯难了。

数据范围

本题采用捆绑测试

对于 $100\%$ 的数据，保证 $1\le n\le 5\times 10^3$，$1\le a_i\le 5\times 10^3$。