You are given a multiset $S$. Each element in the multiset is an integer between $-N$ and $N$ (inclusive), where $i$ appears $a_i$ times in the multiset.

In each operation, you choose two different elements of the multiset, $X$ and $Y$, such that $|X-Y|=2$. Then, $X$ and $Y$ will be deleted from the multiset, and $\frac{X+Y}{2}$ will be added to the multiset twice.

Find the minimum number of operations such that every element of $S$ is equal to $0$. The data guarantees that such a sequence of operations will exist.

Constraints

$1\le N\le 5\times {10}^5$

$0\le \sum a_i\le {10}^{18}$

Input Specification

The first line contains an integer, $N$.

The next line contains $2N+1$ integers, $a_{-N},a_{-N+1},\dots ,a_N$.

Output Specification

Output the minimum number of operations to set all elements to $0$ modulo ${10}^9+7$.

Sample Input

2
1 1 1 1 1

Sample Output

5

Explanation for Sample

Let's keep track of the elements in the multiset after each operation.

Initially, the multiset has the elements $\{-2,-1,0,1,2\}$ within it.

1. Choose $X=2$ and $Y=0:\{-2,-1,1,1,1\}$
2. Choose $X=1$ and $Y=-1:\{-2,0,0,1,1\}$
3. Choose $X=-2$ and $Y=0:\{-1,-1,0,1,1\}$
4. Choose $X=-1$ and $Y=1:\{-1,0,0,0,1\}$
5. Choose $X=-1$ and $Y=1:\{0,0,0,0,0\}$

It can be proven that $5$ is the minimum number of operations required to set everything to $0$.