Rikka with XOR

Rikka가 어렸을 때 「A good task to defend AK」라는 어렵지만 흥미로운 문제를 만났다. 그 문제에서는 XOR(배타적 논리합, 기호 $\oplus$)의 성질 여러 가지가 쓰였다.

여섯 해가 지나 Rikka는 대학생이 되었다. 오늘 Rikka는 그 문제를 떠올렸고, XOR에 대해 아는 것이 거의 없다는 사실을 깨달았다. 그래서 XOR에 관한 문제를 직접 만들어 풀어 보려 했다.

대부분의 문제는 아주 간단했지만 하나만은 예외였다. Rikka는 그 문제가 너무 어렵다고 느꼈고, 도움을 청했다.

정수 $n$과 $m$이 주어졌을 때, $\prod_{i=0}^{m} (n \oplus i)$를 계산하라. 답이 매우 클 수 있으므로 소수인 $1\,500\,000\,001$로 나눈 나머지를 구하라.

첫 번째 줄에 테스트 케이스의 개수를 뜻하는 정수 $t$ ($1 \leq t \leq 20$)가 주어진다.

각 테스트 케이스는 한 줄에 정수 $n$과 $m$ ($1 \leq m < n \leq 10^9$)이 주어진다.

각 테스트 케이스마다 답을 $1\,500\,000\,001$로 나눈 나머지를 한 줄에 출력한다.