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~.