David 是一个小孩。他喜欢玩组合游戏，例如尼姆游戏（Nim game）。他虽然只是个业余爱好者，但在博弈论方面却很有造诣。这一次，他为你准备了一个问题。

给定整数 $N, L, R$ 和 $K$，请计算有多少种方法可以构造一个长度为 $N$ 的整数数组，使得其所有元素都在 $[L, R]$（包含边界）范围内，且它们的按位异或和等于 $K$。为了避免计算巨大的整数，请输出方案数对 $(10^9 + 7)$ 取模的结果。

此外，David 希望你针对多个整数 $K$ 进行回答，以确保你的解法完全正确。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量。 接下来描述所有测试用例。对于每个测试用例： 第一行包含四个空格分隔的整数 $N, L, R$ 和 $Q$，表示有 $Q$ 次查询，这些查询具有相同的 $N, L, R$，但 $K$ 不同。 第二行包含 $Q$ 个空格分隔的整数，表示多个 $K$ 的值。

$1 \le T \le 1000, 1 \le N \le 10^9, 0 \le L \le R < 2^{30}, 1 \le Q \le 100, 0 \le K < 2^{30}$。 保证不超过 100 个测试用例不满足 $1 \le N \le 15, 0 \le L, R, K < 2^{15}$。

输出格式

对于每次查询，在一行中输出答案对 $(10^9 + 7)$ 取模的结果。

样例

输入 1

3
2 3 4 2
0 7
3 3 4 2
3 4
5 5 7 4
5 6 7 8

输出 1

2
2
4
4
61
61
61
0

说明

在第一个样例中，有两种方法选择一个数字 3 和一个数字 4，使得它们的异或和为 7。

在第二个样例中，有三种方法选择一个数字 3 和两个数字 4，以及一种方法选择三个数字 3，使得它们的异或和为 3。