All Tracks Math Number Theory Problem

Walter White's Special Compounds
Tag(s):

Math, Medium, Medium, Number Theory

Problem
Editorial
Analytics

One fine day Walter White was busy making some special compounds in his lab. These compounds have some special properties. These are straight chain compounds consisting of only 2 types of elements '0' and '1'. Also elements to same type cannot share a bond. So some of the compounds are named as '1' , '101' , '0'.

enter image description here

Now he assigns a secret key to each element. Secret key is simply the decimal representation of the compound name(eg. secret key for compound '101' is 5). These compounds are to be stored in different storage containers numbered from 1 to infinity (1,2,3,4,......) in increasing order of their secret key (i.e compound with secret key 0 is stored in container 1, compound with secret key 1 is stored in container 2 .... so on ).

Walter White needs your help for storing the compounds. You are given the container number n and you have to tell him the secret key of the compound corresponding to that container. Since the secret key can be very large output it modulo 1000000007.

INPUT

The first line contains an integer T denoting the number of test cases.
T test cases follows each containing a single integer n.

OUTPUT

For each test case output the answer to the question in separate line.

CONSTRAINTS

1<=T<=10^5
1<=n<=10^9

SAMPLE INPUT
3
1
2
7
SAMPLE OUTPUT
0
1
42
Time Limit: 1.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

Notifications
View All Notifications