Bob was given N integers by his teacher. He was supposed to make a expression out of them without changing the order of integers. So he decided to use 2 types of operators: "$|$"(also known as Bitwise Or ) and "$+$". He decided to put exactly one operator between every consecutive integers. Thus he would use $N-1$ operators to form a valid mathematical expression from the N integers. But as Bob is feeling very sleepy, he might use any of the 2 operators with equal probability at any of the valid places.

His teacher was perplexed by this random behavior and wondered what is the Expected value of the Random Expression thus created by her student. Note that Bitwise OR has higher precedence than addition operator.

Input Format

The first line consists of an integer, N.
Next line follows with N integers.

Output Format

Print $P * Q^{-1} mod\space10^9+7$, where $\frac{P}{Q}$ is the expected value of expression expressed as an irreducible fraction.

Input Constraints

$1 \le N \le 10^6$
$0 \le all\space integers \le 10^9$