Rikka with XOR
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 512000/512000 K (Java/Others)Total Submission(s): 16 Accepted Submission(s): 0
Problem Description
When Rikka was a little girl, she met a hard but interesting problem "A good task to defend AK." This problem uses some properties about XOR $\oplus$ (exclusive OR).
Time flies, six years have passed. Rikka has become a college student. And today, Rikka recollects this task and she finds herself know little about XOR. So she wants to come up with some tasks about XOR and try to solve them.
Most of the tasks are very simple, except one of them. Soon, Rikka finds it is too difficult for her. So she asks you to give her some help. Here is the task:
Given two integers $n,m$, and she wants to calculate $\prod_{i=0}^m n \oplus i$. The answer may be very large, she just wants to know the answer modulo $1500000001$.
Time flies, six years have passed. Rikka has become a college student. And today, Rikka recollects this task and she finds herself know little about XOR. So she wants to come up with some tasks about XOR and try to solve them.
Most of the tasks are very simple, except one of them. Soon, Rikka finds it is too difficult for her. So she asks you to give her some help. Here is the task:
Given two integers $n,m$, and she wants to calculate $\prod_{i=0}^m n \oplus i$. The answer may be very large, she just wants to know the answer modulo $1500000001$.
Input
The first line contains one single integer $t(1 \leq t \leq 20)$, the number of the testcases.
For each testcase, the first line contains two integers $n,m(1 \leq m < n \leq 10^9)$.
For each testcase, the first line contains two integers $n,m(1 \leq m < n \leq 10^9)$.
Output
For each testcase, output a single integer, the answer modulo $1500000001$ which is a prime number.
Sample Input
3 3 2 7 5 654321 123456
Sample Output
6 5040 1230647278