题目描述

题目译自 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\ (1\le n\le 5\cdot 10^3)$，表示 Bytie 有的袋装糖果数量。

第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n\ (1\le a_i\le 5\cdot 10^3)$，表示每袋糖果中糖果的数量。

输出格式

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

5
2 7 4 4 1

8