I. Krosh and one more problem with xors
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Krosh has the array $$$a$$$ of $$$n$$$ non-negative integers. Help him to calculate the following value:

$$$\sum\limits_{l = 1}^n \sum\limits_{r = l}^n (a(l) $$$ $$$^$$$ $$$a(l + 1) $$$^$$$ $$$... $$$^$$$ $$$a(r)) * max(a(l), a(l + 1), ..., a(r))$$$ (^ - bitwise XOR).

Output the answer modulo $$$10^9+7$$$.

Input

In the first line you are given number $$$1 \le n \le 2 * 10^5$$$ In the next line you are given $$$n$$$ non-negative integers $$$0 \le a_i \le 10^9$$$.

Output

Output the answer modulo $$$10^9+7$$$.

Examples
Input
4
10 8 12 1
Output
941
Input
1
1000000000
Output
49