当 Rikka 还是个小女孩时，她遇到过一道既困难又有趣的题目“A good task to defend AK”。这道题利用了异或（XOR，一种二进制运算，记作 $\oplus$）的一些性质。

时光飞逝，六年过去了。Rikka 已经成为了一名大学生。今天，Rikka 回忆起了这道题，突然意识到自己对异或的了解少之又少。于是，她想出了一些关于异或的问题并尝试解决它们。

大部分问题都很简单，但其中有一个例外。很快，Rikka 发现它太难了，所以她请求你帮帮她。

题目如下：给定两个整数 $n$ 和 $m$，计算 $\prod_{i=0}^{m} (n \oplus i)$。答案可能非常大，因此请将其对 $1\,500\,000\,001$（这是一个质数）取模。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 20$)，表示测试用例的数量。

每个测试用例占一行，包含两个整数 $n$ 和 $m$ ($1 \le m < n \le 10^9$)。

输出格式

对于每个测试用例，输出一个整数：答案对 $1\,500\,000\,001$ 取模的结果。

样例

样例输入 1

3
3 2
7 5
654321 123456

样例输出 1

6
5040
1230647278