小红在黑板上写了一个计算式，具体来讲是 个数字 ，其中间由 个加号（）连接组成：。
现在小苯想去擦去黑板上的一些 运算符，但他擦得很不干净，只擦去了加号中的横线（），剩下的部分就是一个竖线（）了。巧合的是， 恰好也是一个运算符：按位或 。
小苯想知道，有多少种不同的擦黑板方式，能使得按照新算式进行计算，结果和擦黑板前的算式计算结果相同，请你帮他算一算。注意，不擦黑板也是一种方案。由于答案可能很大，请将答案对 取模后输出。

【注】
特别的，在本题中我们认为 运算符的优先级大于加法运算 。
两种擦黑板方式不同当且仅当存在至少一个运算符位置，其在其中一个方式中为 ，而在另一个方式中为 （即按位或 ）。

【名词解释】
：指位运算中的按位或（Bitwise OR），对两个整数的二进制表示按位进行或运算。如果您需要更多位运算相关的知识，可以参考 OI-Wiki的相关章节。

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

第一行输入一个整数 ，表示黑板上的数字个数。
第二行输入  个整数 ，表示黑板上的数字。

除此之外，保证单个测试文件的  之和不超过 。

对于每一组测试数据，新起一行输出一个整数，表示不同的擦黑板方案个数对  取模后的答案。

3
2
1 2
3
1 2 3
4
1 2 0 4

2
2
8

对于第一组测试数据，对于  这个计算式：
我们可以选择擦中间的 ，就能得到：，原式运算结果也为 ，因此是一种方案；
不擦黑板显然是一种方案。
综上，共有两种方案。