Bajtek 要去参加 Bitek 的生日派对。他知道 Bitek 非常喜欢甜食，因此想送给他一些糖果包装袋作为礼物。他买了 $n$ 个包装袋，其中第 $i$ 个包装袋里有 $a_i$ 颗糖果。

这些包装袋相当沉重，Bajtek 在考虑是否一定要把它们全部带给 Bitek。他决定选择一个非空的包装袋子集，带去给 Bitek，并对他说：“我这里总共有 $x$ 颗糖果，你想要多少？”其中 $x$ 是他带去的包装袋中糖果的总数。Bitek 听到这个问题后，很可能会选择区间 $[1, x]$ 中的任意整数 $y$。Bajtek 希望无论 Bitek 选择什么数字，他都能从带去的包装袋中选出一部分（剩下的留给自己），使得这些包装袋中的糖果总数恰好为 $y$。当然，这里不能拆开包装袋——不带包装直接给糖果是不礼貌的。

因此，Bajtek 想知道他有多少种非空的包装袋子集可以选择，以便无论寿星如何选择，他都能满足对方的要求。请帮他计算这个数量！由于这样的子集数量可能非常大，你只需要输出其对 $10^9 + 7$ 取模后的结果。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 5000$)，表示 Bajtek 拥有的糖果包装袋数量。

第二行包含一个由 $n$ 个整数组成的序列 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 5000$)，表示 Bajtek 每个包装袋中的糖果数量。

输出格式

输出一个整数，表示 Bajtek 可以带给 Bitek 的满足条件的包装袋子集数量，结果对 $10^9 + 7$ 取模。

样例

输入 1

5
2 7 4 4 1

输出 1

8

说明 1

Bajtek 可以带给 Bitek 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\}$。如果他决定带上第一、第二、第四和第五个包装袋，而 Bitek 想要 9 颗糖果，他只能送出第一和第二个包装袋。Bajtek 不能选择只带第一、第二和第五个包装袋，因为如果 Bitek 想要 6 颗糖果，Bajtek 将束手无策。