C. Coconuts
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Leo Angels loves coconuts. He wants to drink coconut water in Good Trip beach. Between every block in Good Trip avenue there is a kiosk with one drink which could be coconut water. Coconuts can taste better than others, being sweeter or colder, each of them having its corresponding satisfaction value. Every block has a street parallel to the avenue, in which Leo could enter or exit. He wants to enter the avenue once at any street and get every drink available until his exit.

Leo starts the day with satisfaction $$$s = 1$$$ and every time he gets a drink with satisfaction $$$d$$$, his new satisfaction becomes $$$s \times d$$$.

Oel knows Leo loves coconuts and changed some of them to Leopsi Zero and sparkling water. Leo hates sparkling water and it always has a negative satisfaction value. However, if his current satisfaction is negative, drinking sparkling water makes it positive again, because life can't be as bad as sparkling water.

When Leo drinks Leopsi Zero, he passes out and his satisfaction becomes zero, because although it is zero calories it doesn't have zero sodium.

Every drink has a satistaction value in the form $$$|2^{k}|$$$ except for Leopsi Zero which is $$$0$$$.

Find the greatest satisfaction he can get in a day modulo $$$10^9 + 7$$$.

Input

The input consists of two lines.

The first line is an integer $$$n$$$ ($$$1\le n \le 2 \cdot 10^5$$$), the number of blocks in the shore.

The second line contains $$$n$$$ integers describing the satisfaction value of each kiosk's available drink $$$a_1, a_2, ... ,a_n$$$ ($$$|a_i| \lt = 2^{30}$$$) and $$$|a_i|$$$ is either $$$0$$$ or in the form $$$\pm 2^{k}$$$.

Output

You must output one line:

The first and only line contains an integer, the greatest satisfaction value modulo $$$10^9 + 7$$$

Examples
Input
3
0 -1 0
Output
1
Input
6
8 -1 -2 0 2 4
Output
16
Input
6
8 1 2 0 8 2
Output
16
Note

In the first sample, Leo can choose not to go to the beach and keep his satisfaction at $$${1}$$$.

In the second sample, the greatest satisfaction is $$${16}$$$, and can be achieved by entering in the first block and leaving after third block.