G. 1-05G.mob的《麻将与概率系统导论》

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

题目描述

在打麻将的同时,mob也在十分刻苦地学习《概率论与数理统计》,他逐渐从书本和麻将实践中得到了一些启发,发现麻将的概率问题复杂性来源于其模型的高度复杂性,于是他试图发明一套新的概率方法来求解这些过于复杂的概率和统计问题。功夫不负有心人,他最终找到了规律并发明了一种他称之为“概率系统”的理念,其中有一种统计问题是整个理论的核心:

个概率模式,每个概率模式有两个参数,这个概率模式组成全集,对任何一个的子集,我们称它的mob值为:中所有概率模式对应的的异或和。此外,我们称是合法的当且仅当:中所有概率模式所对应的两两按位与的结果均为,我们称一个出现的概率为中所有概率模式对应的的积。

为了验证你是否掌握了这套概率系统理论,mob给了你个询问,每个询问都给出一个,询问:

所有值为的合法子集的出现概率之和为多少?

由于这个数可能很大,你只需要输出答案对 取模的结果即可

输入格式

第一行一个正整数,表示概率模式数

行每行两个正整数,分别表示第种概率模式的两个参数

接下来一行一个正整数表示询问个数

接下来行每行一个正整数,表示询问

输出格式

输出行,第行一个正整数表示第次询问的答案

样例

样例输入 样例输出
3
1 1
1 2
1 3
3
1
2
3
1
1
2

数据范围与提示