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 取模后的值。

样例 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。

Potyczki