小苯有一个长度为 的序列 ，他认为一个序列的权值为：序列中所有数字的按位与。 现在小苯想知道所有的非空（显然一共 个）的子序列中，有多少个子序列的权值是偶数，请你帮他算一算吧。由于答案可能很大，请将答案对 取模后输出。 【名词解释】 按位与（Bitwise AND）：对两个整数的二进制表示按位进行与运算。如果您需要更多位运算相关的知识，可以参考 OI-Wiki的相关章节。 子序列：从原序列中删除任意个（可以为零、可以为全部）元素得到的新序列。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数 代表数据组数，每组测试数据描述如下：第一行一个正整数 ，表示序列的长度。第二行 个非负整数 ，表示序列中的元素。除此之外，保证单个测试文件的 之和不超过 。

输出描述:

对于每一组测试数据，新起一行输出一个整数，表示权值为偶数的子序列个数对 取模后的值。