Cukierki

Bytie is heading to Bitek's birthday party and has bought n bags of candies. The i-th bag contains a_i candies. However, since the bags are heavy, Bytie wonders if he really needs to bring them all. He decides to choose a non-empty subset of these bags and tell Bitek, "I have a total of \(x\) candies. How many would you like?" where \(x\) is the sum of candies in the chosen bags.

Bitek may respond with any integer \(y\) in the interval \([1, x]\). No matter his choice, Bytie wants to be able to hand over some of the bags (without opening any bag) so that the candies contained in them sum exactly to \(y\). In other words, from the chosen bags, for every integer \(y\) with \(1 \le y \le x\), there exists a sub-selection whose total candy count is exactly \(y\).

Your task is to count how many non-empty subsets of bags (by index) satisfy this condition. Because the answer might be very large, output it modulo \(10^9+7\).

inputFormat

The input begins with an integer n (the number of candy bags). The next line contains n space-separated integers \(a_1, a_2, \dots, a_n\), where \(a_i\) denotes the number of candies in the i-th bag.

outputFormat

Output a single integer — the number of valid non-empty subsets of bags modulo \(10^9+7\).

sample

3
1 1 1

7