题目描述

llh 最近学习了二叉排序树：对于树上的任意一个点，如果其存在左子树，则其左子树中所有点的数字都必须小于等于该点的数字；如果其存在右子树，则其右子树中所有点的数字都必须大于等于该点的数字。

现在 llh 拿到了 $n$ 个正整数，他想用这些数字建立一棵二叉排序树，但是他给自己定了一个有趣的规则

他希望这棵树中任意一条简单路径（至少包含 $2$ 个节点)上的任意相邻两个数字的乘积，在二进制下 $1$ 的个数为奇数个

现在他想知道有多少种方案可以构造这样的一棵二叉排序树？

这里我们认为两个数即使下标不同，只要它们的值相同，则计算方案数时就认为它们相同。

例如：$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