题目描述

有些人在社交网络中使用过许多的密码，我们通过将各种形式的信息转化为 01 信号，再转化为整数，可以将这个人在一段时间内使用过的密码视为一个长度为 $n$ 的非负整数序列 $a_1,a_2,\cdots,a_n$。一个人相邻几次在社交网络中使用的密码很有可能是类似的，这使得密码并不是足够安全。为了检验某些人在某些时间段内是否可能受到不安全的影响，我们需要计算上述序列的复杂程度。

定义 $f(L,R)=\max(a_L,A_{L+1},\cdots,a_R)$，$g(L,R)=a_L \operatorname{xor} a_{L+1}\operatorname{xor}\cdots\operatorname{xor}a_R$。

请你帮忙计算 $\sum\limits_{L=1}^n\sum\limits_{R=L}^nf(L,R)g(L,R)$ 的值，这将作为我们评估密码复杂程度的一个部分。由于答案可能很大，你只需要给出答案对 $10^9+61$ 取模的值即可。

输入格式

第一行包含一个正整数 $T$，表示有 $T$ 组测试数据。
接下来依次给出每组测试数据。对于每组测试数据：
第一行包含一个正整数 $n$。
第二行包含 $n$ 个非负整数，表示 $a_1,a_2,\cdots,a_n$。
保证在一行中的每个整数之间有恰好一个空格，没有其他额外的空格。

输出格式

对于每组数据输出一行，包含一个整数，表示答案对 $10^9+61$ 取模的值。

3
1
61
5
1 2 3 4 5
5
10187 17517 24636 19706 18756

3721
148
821283048

数据规模与约定

对于 $100\%$ 的数据，$1\le T\le 200$，$1\le n\le 10^5$，$1\le\sum n\le10^6$，$0\le a_i\le10^9$。

题目来源

鸣谢 Tangjz 提供试题。