All Submissions


Problem Description

Earth is under attack from the Martians!
The Martians do not attack randomly but they follow a special sequence called "DEIMOS" to plan their attacks. Assume that Earth is divided into many sectors each represented by a unique number. The Nth term of DEIMOS sequence tells you which sector the Martians will attack on day N. Scientists at CERN were able to intercept the communications of the Martians and got the first ten terms of DEIMOS Sequence.
Can you help CERN find out which sector will be attacked on any given day?

The first ten terms of DEIMOS sequence are as follows.
1 2 5 12 29 70 169 408 985 2378



Input

The first line of input contains T, the number of test cases.
Each test case contains an integer N, the day of attack.

Output

Your task is to find S, the sector which the Martians will attack on day N.
For each test case, output S modulo 1000000007 followed by a new line.

Constraints
  • 1 <= T <= 1000
  • 1 <= N <= 109


Sample Input


5
2
5
9
19
12


Sample Output


2
29
985
6625109
13860


Problem Setter: Rohan Laishram

Languages: C,C++,Java

Time Limit: 1 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Submit

Login to post clarification.

No Clarifications.

Contest

Mode Judge

Passive

Online

Overall Rankings

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0