SOLVE

LATER

GCD Strings

/

Let \(P[0 \dots N-1]\) be a binary string of length *N*. Then let's define \(S^{\infty}(P)\) as an infinite string with \(S^{\infty}[i] = P[i\%N] \space \forall\space i ≥0\) (informally, \(S^{\infty}(P)\) is the concatenation of *P* with itself an infinite number of times).

Define the **GCD-string** of two integers \(a, b\), with \(a \geq b\) to be a binary string of length *a* that satisfies the following:

- \(g(a,b)\) = \(100\dots 000\) (
*1*followed by \(a-1\) zeros ) if*a*is divisible by*b* - \(g(a,b)\) = First
*a*characters of \(S^{\infty}(g(b, a \space mod\space b))\) otherwise

We can define \(F(a,b)\) to be the value of the integer represented by the binary string \(g(a,b)\) in **base-2**.
Given *T* pairs of integers \((x,y)\), compute \(F(x,y)\space mod\space 10^9+7\) for each pair.

The first line will contain the number of test cases *T*.

Each test case can be described with a single line containing two integers \(x,y\).

Output *T* numbers, the answers to each problem.

For all subtasks:

\(T ≤ 10^4\)

\(1 ≤ y ≤ x\)

**File 1 (70 pts)**

\(x ≤ 100\)

** File 2 (30 pts)**

\(x ≤ 10^9\)

Explanation

The base 2 results for the first four samples are as follows

- \(100\)
- \(101\)
- \(10101\)
- \(1000100010\)

Time Limit:
2.0 sec(s)
for each input file.

Memory Limit:
256 MB

Source Limit:
1024 KB

Initializing Code Editor...