暂无测试数据。

一个 BST 是一个二叉树，每个点有一个数字；对于 BST 中的任意一个点，如果其存在左子树，则其左子树中所有点的数字都必须小于等于该点的数字；如果其存在右子树，则其右子树中所有点的数字都必须大于等于该点的数字。

给定 $n$ 个正整数 $a_i$，要将这些数建成一个 BST，使得 BST 中任意一条点数不小于 $2$ 的路径上的任意相邻两点的数字的乘积的二进制表示中有奇数个 $1$，求方案数模 $10^9+7$。

两个数只要下标不同（尽管它们的值可能相同），则计算方案数时就认为它们不同。例如：$n=2$，$a_1=1,a_2=1$，则方案数为 $2$。

输入格式

第一行一个正整数 $T$，表示测试数据的组数。

每组数据中，第一行一个正整数 $n$，第二行 $n$ 个正整数 $a_i$。

输出格式

$T$ 行，表示对应的方案数模 $10^9+7$。

数据范围

对于 $20\%$ 的数据，$n\le 10$。

对于 $40\%$ 的数据，$n\le 20$。

对于 $60\%$ 的数据，$n\le 50$。

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

2
3
1 2 3
3
7 2 1

0
5