题目描述

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

这个新世纪共有 $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$ 求余的结果。

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

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

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

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

形式化地：

有 $n$ 个节点，第 $i$ 个节点的权值为 $a_i$，其中一个节点作为根节点，每一个节点会有至多一个 $A$ 关系子节点和至多一个 $B$ 关系子节点，$A$ 关系和 $B$ 关系都是单向的，满足：

• 所构成关系图不存在环。

• 一个节点的 $A$ 关系子节点下的子连通图每一个节点权值均不大于该节点；一个节点的 $B$ 关系子节点下的子连通图每一个节点权值均不小于该节点。

• $n$ 个节点构成一个分层图，根节点居中，一个节点的 $A$ 关系子节点在其下一层，$B$ 关系子节点在其上一层。

所构成的关系图中，任意一条简单路径（无分支，相当于链），相邻的两个节点权值乘积 $m$ 满足 $\bigoplus_{k=0}^{\lfloor \log_2 m \rfloor} \left( (m \gg k) \mathbin{\&} 1 \right) = 1$。

求这 $n$ 个节点所能构成分层图的方案数对 $1e9 + 7$ 求余的数。

不同方案定义如下：

• 根节点不同、任意一条 $A$、$B$ 关系不同、任意一个节点编号不同，视为不同方案。

• 同一层的节点只要编号相同，即视为同种方案。

输入格式

本题包含多组数据。

第一行一个整数 $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

样例解释

对于上述样例第二组数据，满足条件的图有：

$2$ 为根节点，$7$ 是 $2$ 的 $B$ 关系子节点，$8$ 是 $7$ 的 $B$ 关系子节点。

$2$ 为根节点，$8$ 是 $2$ 的 $B$ 关系子节点，$7$ 是 $8$ 的 $A$ 关系子节点。

$7$ 为根节点，$2$ 是 $7$ 的 $A$ 关系子节点，$8$ 是 $7$ 的 $B$ 关系子节点。

$8$ 为根节点，$7$ 是 $8$ 的 $A$ 关系子节点，$2$ 是 $7$ 的 $A$ 关系子节点。

$8$ 为根节点，$2$ 是 $8$ 的 $A$ 关系子节点，$7$ 是 $2$ 的 $B$ 关系子节点。

数据规模与约定

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

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