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.
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.
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\).
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\)
3 1 2 3
1 4 13