Bingbong的幻想世界
题号：NC269155
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

世界之大，遇见你
    如同星辰相撞，闪耀璀璨
🌙我什么时候能与月色相比，穿过重重山河相拥你
Bingbong有一个长度为n数组a。

对于一个区间[l,r]的权值w定义为:w=\sum _{i=l}^{i=r}\sum_{j=l}^{j=r} a_i \oplus a_j

\oplus:位运算中的按位异或

现在需要求出数组a中所有非空子区间的权值之和，结果对10^9+7取模。


输入描述:

第一行一个整数n (1\leq n\leq 2\times 10^5)，代表数组长度。

第二个n个整数，a_1,a_2,...,a_n (0 \leq a_i\leq 10^6)。

输出描述:

一个整数，表示最后的答案。
示例1

输入

复制 
6
1 1 4 5 1 4

输出

复制 
422