408035: GYM102964 I Krosh and one more problem with xors

Memory Limit:256 MB Time Limit:3 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

I. Krosh and one more problem with xorstime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard 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$$$.

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

加入题单

上一题 下一题 算法标签: