Sequences

Consider a sequence of integers $a_1, ..., a_k$. We call the value of $a_1, ..., a_k$, which we denote by $(a_1, ..., a_k)$, the maximal integer $2^x = \underbrace{2 \times ... \times 2}_{x \text{ times}}$ such that $2^x$ divides $a_1 + ... + a_k$. For example, if $k = 3$ and $a_1 = 8, a_2 = 3, a_3 = 1$ then $a_1 + a_2 + a_3 = 12$ and the value of the sequence is $4$.

You are given a sequence of $n$ positive integers $a_1, ..., a_n$. Calculate the remainder sum of the value of all the contiguous subsequences of $a_1, ..., a_n$ when divided by $10^9 + 7$, which is equal to
$\displaystyle S(a_1, ..., a_n) = \sum_{i=1}^{n} \sum_{j=i}^{n} (a_i, ..., a_j) \ (\text{mod } 10^9 + 7)$

In other words, $S(a_1, ..., a_n)$ is the remainder of the sum of $(a_i, ..., a_j)$ for $1 ≤ i ≤ j ≤ n$ when divided by $10^9 + 7$.

Input data

The first line of the input contains the integer $n$. The second line of the inputs contains the integers $a_1, ..., a_n$, separated by white space.

Output data

The output must contain a single line, which contains the integer $S(a_1, ..., a_n)$.

Restrictions

• $1 ≤ n ≤ 200 \ 000$.
• $1 ≤ a_i ≤ 1 \ 000 \ 000$.
• $a_1 + ... + a_n ≤ 1 \ 000 \ 000$.

Subtask 1 (13 points)

• $a_i = 1, n ≤ 200$

Subtask 2 (16 points)

• $a_1 + ... + a_n ≤ 200$

Subtask 3 (5 points)

• $n ≤ 200$

Subtask 4 (20 points)

• $n ≤ 5 \ 000$

Subtask 5 (21 points)

• $a_1 + ... + a_n ≤ 200 \ 000$

Subtask 6 (25 points)

• No further restrictions

Examples

stdin

3
1 2 3

stdout

8

stdin

5
2 4 1 2 4

stdout

25

stdin

20
1 2 3 1 2 3 4 5 6 2 3 3 1 2 3 7 5 1 2 3 2

stdout

728

Explanations

First example: The values of all the contiguous subsequences are:

• $(1) = 1$
• $(1, 2) = 1$
• $(1, 2, 3) = 2$
• $(2) = 2$
• $(2, 3) = 1$
• $(3) = 1$
  Thus $S(1, 2, 3)$ is the remainder of sum of these values when divided by $10^9 + 7$ i.e. $8$.

Second example: The values of all the contiguous subsequences are:

• $(2) = 2$
• $(2, 4) = 2$
• $(2, 4, 1) = 1$
• $(2, 4, 1, 2) = 1$
• $(2, 4, 1, 2, 4) = 1$
• $(4) = 4$
• $(4, 1) = 1$
• $(4, 1, 2) = 1$
• $(4, 1, 2, 4) = 1$
• $(1) = 1$
• $(1, 2) = 1$
• $(1, 2, 4) = 1$
• $(2) = 2$
• $(2, 4) = 2$
• $(4) = 4$
  Thus $S(2, 4, 1, 2, 4)$ is the remainder of the sum of these values when divided by $10^9 + 7$ i.e. $25$.