#1046. 城市道路

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: tony102

题目描述

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% 的数据,