小苯的子数组权值2.0
题号：NC281042
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小苯有一个长度为 n 的数组 a。他定义：
f(a) = a_1\ \oplus \ a_2 \ \oplus ... \oplus \ a_n。（即所有数字的异或和）。
g(a) = gcd(a_1, a_2, ... ,a_n)。（即所有数字的最大公约数）。

现在小苯希望你求出数组a 的所有子数组（需满足连续）的 f \cdot g 值之和。

输入描述:

每个测试文件内都包含多组测试数据。
第一行一个正整数 T\ (1 \leq T \leq 100)，表示测试数据的组数。
接下来对于每组测试数据，输入包含两行。
第一行一个正整数 n\ (1 \leq n \leq 2 \times 10^5)，表示数组 a的长度。
第二行 n 个整数 a_i\ (0 \leq a_i \leq 10^9)，表示数组 a。
（保证所有测试数据中 n 的总和不超过 3 \times 10^5。）

输出描述:

对于每组测试数据，输出一行一个整数表示所有子数组的f \cdot g 值之和。（由于结果可能很大，因此输出结果对 1000000007 取模的值。）
示例1

输入

复制 
1
5
1 2 3 4 5

输出

复制 
79