题目描述

诺坦菲亚圣甲虫在赫陶世界被誉为最具灵性的祈福生物，其身金灿熠光，有着尊卑等级，人类通过解读，将这种等级命名为苏罗氏值，每当新世纪的天音传响于广袤大地，诺坦菲亚圣甲虫便会以人类难以理解的阵型，恍若在举行某种仪式。

这个新世纪共有 $n$ 只诺坦菲亚圣甲虫举行仪式，第 $i$ 只诺坦菲亚圣甲虫的苏罗氏值为 $a_i$。

诺坦菲亚圣甲虫中的某一只会在新世纪被推举为轴承牧师。

每只诺坦菲亚圣甲虫会有至多一个附庸与至多一个星君：

• 其附庸永远站在其后面一行，其星君永远站在其前面一行。

• 其附庸、附庸的星君、附庸的附庸等与其附庸有直接或间接关系的苏罗氏值永远不高于它，其星君、星君的星君、星君的附庸等与其星君有直接或间接关系的苏罗氏值永远不低于它。

• 当然，有的诺坦菲亚圣甲虫没有附庸，有的没有星君，有的甚至两者皆无，但除了轴承牧师外的每一只圣甲虫一定是某只圣甲虫的附庸或星君。

因此，可以在这些诺坦菲亚圣甲虫中找到许多条庸主关系链，也就是以某只诺坦菲亚圣甲虫为起点，寻找若干次其星君或附庸组成的一条链，这个链的诺坦菲亚圣甲虫至少有 $2$ 只，它们希望 $n$ 只诺坦菲亚圣甲虫排好阵形后有如下约束：

• 对于任意一条庸主关系链中，相邻的两只诺坦菲亚圣甲虫苏罗氏值乘积 $m$ 满足 $\bigoplus_{k=0}^{\lfloor \log_2 m \rfloor} \left( (m \gg k) \mathbin{\&} 1 \right) = 1$。

如果你不理解 $\bigoplus$ 的含义，请看：

• 类似于求和，只不过这里是把全体的 $\left( (m \gg k) \mathbin{\&} 1 \right)$ 进行逻辑异或运算级联，白话说就是所有 $\left( (m \gg k) \mathbin{\&} 1 \right)$ 的异或和。

现在你需要求出以上约束下 $n$ 只诺坦菲亚圣甲虫可以有多少种不同阵型，由于这个数可能很大，你只需要输出其对 $1e9 + 7$ 求余的结果。

这里对于不同的定义是这样的：

• 只要有任意一只诺坦菲亚圣甲虫不同，那就是不同。

• 如果有任意一对附庸或星君关系不同，那么也称之为不同。

• 在同一行的诺坦菲亚圣甲虫，视为同种阵型。

输入格式

本题包含多组数据。

第一行一个整数 $T$，数据组数。

接下来对于每组数据输入 $2$ 行：

第一行一个整数 $n$，为诺坦菲亚圣甲虫总数。

第二行 $n$ 个整数，第 $i$ 个整数 $a_i$ 表示第 $i$ 只诺坦菲亚圣甲虫的苏罗氏值。

输出格式

一个整数，表示不同阵型数对 $1e9 + 7$ 求余的结果。

3
4
1 3 5 7
3
2 7 8
2
4 4

0
5
2

数据规模与约定

对于 $40 \%$ 的数据满足 $1 \le n \le 20$。

对于 $100 \%$ 的数据满足 $1 \le n \le 200，T = 3，1 \le a_i \le 10^9$。