G. 城市道路

A 国一共有 个城市，编号分别为 。

在国家建立之初，政府需要给这 个城市之间修一些道路。A 国的国王很喜欢二进制，他首先给每个城市一个数字，第 个城市的数字是 。之后，对于任意两个城市 ，他会从城市 往城市 连接 条**单向**路径。各个符号的含义见题面末尾。

现在国王想知道：从城市 出发前往城市 ，一共有多少条路径？由于答案可能会很大，你需要输出答案对 取余数之后的结果。

函数 表示 的二进制表示中 的个数，例如 。

表示二进制与运算，二进制与运算的规则是，只有当两个数的对应位都为 时，结果才为 ；否则结果为 。换句话说，如果某个位上的数都是 ，则结果位也为 ；否则结果位为 。例如下面的运算：

  10101010
& 11110000
-----------
  10100000

第一行输入一个正整数 ，表示数据组数。

对于每一组数据，第一行输入一个正整数 ，表示城市数。

第二行输入 个正整数 。

对于每一组数据，输出一行一个整数，表示从城市 到城市 的路径数，对 取余数之后的结果。

样例输入

3
4
2 3 3 1
5
1 1 1 1 2
10
213672 382909 212809 216719 213980 121009 213899 220021 289002 120390

样例输出

4
0
12433985

样例解释

对于第一组数据，一共有 条路径：

对于第二组数据， 号城市都与城市 没有单向道路，所以路径数是 。

• 对于 20% 的数据，
• 对于 50% 的数据，
• 对于 100% 的数据，。