All Tracks Basic Programming Recursion Recursion and Backtracking Problem

GCD Strings
Tag(s):

Easy, Math, 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

For all subtasks:
\(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: 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, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

December Clash '16

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?