Nick has decided to become a key maker. He has a machine with certain constraints that will be described later. Nick wonders how many different keys shapes he can cut if he starts with a an \(N\) by \(N\) (where \(N\) is a positive integer) sheet of metal subject to the constraints of the machine.

The machine works as follows. It can only cut from the top of the sheet of metal. It does this by way of a square cookie cutter. Nick has square cutters of all integer side lengths which he can mount. The cookie cutter can be moved up and down at integer locations such that only some bottom portion of the square is cut from the sheet of metal. It can also be moved left and right at only integer coordinates. This means a shape like this,

x...xx
x...xx
xxxxxx
xxxxxx
xxxxxx
xxxxxx

is possible. This is because a 3 by 3 cutter could be used to cut out this 2 by 3 section. (Note that 'x' represents uncut, and '.' represents cut.) However, a shape like this,

x.xxxx
x.xxxx
xxxxxx
xxxxxx
xxxxxx
xxxxxx

would not be possible. Since no square cutter could have been lowered to make this. Note that an entire square is allowed to be cut:

x..xxx
x..xxx
xxxxxx
xxxxxx
xxxxxx
xxxxxx

But it is not allowed to cut out a middle portion of the metal:

xxxxxx
xx..xx
xx..xx
xxxxxx
xxxxxx
xxxxxx

Further, for some reason, if Nick makes a cut across some range of columns, then he can never cut from those columns again. So, for example, this shape would not be possible:

xx..xx
xx..xx
xxx.xx
xxxxxx
xxxxxx
xxxxxx

Also, the cutter must be positioned in such a way that it is completely within the range of columns of the sheet of metal. So it would be impossible to make these shapes:

.xxxxx
.xxxxx
.xxxxx
.xxxxx
.xxxxx
.xxxxx


xxxx..
xxxx..
xxxx..
xxxxxx
xxxxxx
xxxxxx

Finally, cutting all the sheet of metal away is considered not to be a valid key shape.

Input Specification

The first line will contain an integer \(T\), the number of test cases to follow. Each test case will consist of a single line containing an integer \(N\), the side length of the sheet of metal Nick has.

Output Specification

For each each test case, output a single line containing an integer, the number of different keys Nick can make. Because this number can be very large, output it modulo \(1000000007\).

Bounds

Note this problem includes sub-problems of increasing difficulty worth different numbers of points:

• 20 points: \(1 \leq N \leq 4\)
• 100 points: \(1 \leq N \leq 50\)
• 200 points: \(1 \leq N \leq 2000\)

\(1 \leq T \leq 5\)

Sample Input

3
1
2
3

Sample Output

1
4
13