暂无测试数据。

花椰妹生日将至，为了给她准备特殊的礼物，蒜头君决定准备一棵树。

蒜头君准备的树十分特别，树的每个节点最多有两个子节点，分别称为左子节点和右子节点。这两个子节点可以为空，也可以存在一个或两个子节点。树上的每个节点都有一个权值。对于树上的每个节点。如果其存在左子树，则其左子树中所有点的数字都必须小于等于该点的数字；如果其存在右子树，则其右子树中所有点的数字都必须大于等于该点的数字。

蒜头君只在商店里准备到了树的原料：长度为 $n$ 的正整数序列 $a$ ，代表蒜头君用来形成蒜头树后蒜头树上的 $n$ 个节点的权值。

蒜头君希望给花椰妹形成的蒜头树不仅满足上面说的特别的性质，并且也满足如下的性质：任意一条点数不小于 $2$ 的路径上的任意相邻两点的数字的异或的二进制表示中有奇数个 $1$ 。

蒜头君希望知道他有多少种组成特别的蒜头树的方案，希望你算一算。

通过估算，蒜头君知道他的方案的数量非常大，于是他希望你输出方案的总数对 $10^9+7$ 取模的结果。

两个数即使下标不同，只要它们的值相同，则计算方案数时就认为它们相同。例如对于仅有三个节点 $a_1=2, a_2=2, a_3=3$ 的情形，以下两种视为同一种情形。

输入格式

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

1
0