GCD Strings
Tag(s):

## Backtracking, Easy, Mathematics, Recursion

Problem
Editorial
Analytics

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.

### Input Format:

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 Format:

Output T numbers, the answers to each problem.

### Constraints

$T ≤ 10^4$
$1 ≤ y ≤ x$

File 1 (70 pts)
$x ≤ 100$

File 2 (30 pts)
$x ≤ 10^9$

SAMPLE INPUT
5
3 1
3 2
5 2
10 4
100 3
SAMPLE OUTPUT
4
5
21
546
986497880
Explanation

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

1. $100$
2. $101$
3. $10101$
4. $1000100010$

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in Challenge Name

December Clash '16

OTHER PROBLEMS OF THIS CHALLENGE
• Math > Game Theory
• Math > Basic Math
• Basic Programming > Implementation
• Math > Combinatorics