Day 2: Ladies First

3.9

57 votes
Easy
Problem

It's 2080. There is a CROWDITORIUM in MANIT Bhopal, the first of its kind.

Generally, Auditoriums are supposed to have the same number of seats in each row, but this one is different.

E.g.

 

  • The seats are grouped column-wise.
  • The first column has ONE seat, the second column has TWO seats and so on until the last i.e. Nth column.
  • The First Row is always reserved for Ladies i.e. the First Seat of each column is reserved for Ladies.
  • The rest of the seats are for Ladies and Gentlemen.

 

One day, Akash, who is very fond of Mathematics, volunteered for a task.

As he got bored by his task, his love for mathematics made him create a problem.

  • He takes ith column of seats and analyses all possible arrangements to populate that column.
  • He sums up the number of ladies he got in each arrangement, this result he calls Si.
  • He then does this for each of the columns from 1 to N.
  • He then has to calculate Sfinal, which is nothing but the summation of Si where i varies from 1 to N.

As Aakash went to play Golf with his friend Mayank, he left the problem unsolved. Can you solve this problem and get a step closer to winning Codathon?

INPUT

The First Line of Input consists of a single positive integer T denoting the number of test cases.

Each of next T lines consists of a single positive integer N denoting the number of columns in the auditorium.

OUTPUT

For each of the test case output a single positive integer denoting Sfinal. As the answer could be large, you have to precisely print Sfinal%1000000007

CONSTRAINTS

 T  106

 N  1018

NOTE: Use Fast I/O technique for large Input.

Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

In case 1, the auditorium has 1 and only seat in a single column and since that is reserved for ladies there is only one way.

L

Sfinal = S= 1

 

In case 2, the auditorium has 1 seat in one column and 2 seats in the second column, the front row of each column is reserved for ladies

There is only one way to fill column 1

L

S1=1

There are two ways to fill column 2

L

G

or

L

L

S2=3

Hence Sfinal=4

Editor Image

?