Derrick is cultivating a garden of $N$ Orz Trees, planted in a line. Derrick's garden can be represented by a sequence of positive integers $H_1,H_2,\dots ,H_N$, with $H_i$ representing the height of the $i^{\text{th}}$ Orz Tree in the line.

Derrick wants to grow more Orz Trees in his garden, but he ran out of Orz Seedlings to plant. Fortunately, Orz Trees aren't like other trees. When an Orz Tree with even height is cut down, two Orz Trees with exactly half the height of the tree appear side-by-side in its place! Note that it is impossible to cut down an Orz Tree with odd height.

Derrick wants to know, after cutting down $0$ or more Orz Trees with even height, how many distinct gardens can he make? Two gardens are distinct if and only if the sequences representing the heights of the trees in the gardens are distinct. Since the answer may be very large, output it modulo ${10}^9+7$.

Constraints

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

$1\le H_i\le {10}^{18}$

Subtask 1 [50%]

$1\le N\le {10}^3$

$1\le H_i\le {10}^3$

Subtask 2 [50%]

No additional constraints.

Input Specification

The first line contains an integer $N$, the initial number of Orz Trees in Derrick's garden.

The second line contains $N$ integers $H_i$, the height of the $i^{\text{th}}$ tree in Derrick's garden.

Output Specification

Output a single integer, the number of distinct gardens Derrick can make by cutting down $0$ or more Orz Trees with even height, modulo ${10}^9+7$.

Sample Input 1

3
6 5 2

Sample Output 1

4

Explanation for Sample Output 1

Derrick can choose to cut down the first and/or last Orz Trees, or to cut down nothing. The $4$ possible gardens he can make are $[6,5,2]$, $[3,3,5,2]$, $[6,5,1,1]$, and $[3,3,5,1,1]$.

Sample Input 2

1
4

Sample Output 2

5

Explanation for Sample Output 2

If Derrick cuts down the tree of height $4$, his garden becomes $[2,2]$. From there, he can choose to cut down either, both, or neither of the trees of height $2$. So, the $5$ possible gardens he can make are $[4]$, $[2,2]$, $[1,1,2]$, $[2,1,1]$, and $[1,1,1,1]$.