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++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, 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