P12828 「DLESS-2」XOR and Number Theory

Given two integers $n$ and $m$. You need to find the sum of $x^2\bmod(y^2-xy)$ over all pairs of integers $(x,y)$ that satisfy the following two conditions: - $1\le x< y\le n$ - $x\oplus y=\gcd(x,y)\le m$ Here, $\oplus$ denotes the bitwise XOR operation. Since the result can be very large, output the answer modulo $10^9+7$.

There are multiple test cases. The first line contains a single positive integer $T$, indicating the number of test cases. For each test case, there is a single line containing two integers, $n$ and $m$.

For each test case, output a single line containing one integer, representing the answer modulo $10^9+7$.

For all test data, it is guaranteed that: - $1\le T\le 3000$ - $2\le n\le 10^9$ - $1\le m\le n$ - $1\le \sum m\le 10^5$ **This problem uses subtasks for grading.** The description for each subtask is as follows: | Subtask | $n\le$ | $\sum n\le$ | $\sum m\le$ | Points | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $1000$ | $1000$ | $1000$ | $10$ | | $2$ | $10^4$ | $10^4$ | $10^4$ | $10$ | | $3$ | $10^7$ | $10^7$ | $10^5$ | $10$ | | $4$ | $5\times10^7$ | $5\times10^7$ | $10^5$ | $20$ | | $5$ | $10^9$ | $+\infty$ | $1000$ | $10$ | | $6$ | $10^9$ | $+\infty$ | $5000$ | $10$ | | $7$ | $10^9$ | $+\infty$ | $3\times 10^4$ | $10$ | | $8$ | $10^9$ | $+\infty$ | $10^5$ | $20$ |