Circuit Board Connections

This problem, including the picture above, was created by Clive Fraser - many thanks!

Consider N components arranged in a straight line on a circuit board. The line runs from left to right. Each of the components has two terminals, one on its left side and the other on its right. We want to connect all of the components into a series circuit, containing a battery, so that current will pass through each component in turn. A single connection will be made to each of the two terminals of a component. No multiple connections are allowed. Only three types of connection are allowed.

For adjacent components a connection can be made directly between them. For example, if component A is adjacent to component B and to the left of component B, we can make a connection from the right terminal of A to the left terminal of B. The first circuit in the diagram shows this type of connection.

Components which are separated by exactly one other component can be connected together. The connection can connect either the left terminals of both components or the right terminals of both components. It is not permitted to connect the left terminal of one of these components with the right terminal of the other. The second circuit in the diagram shows a connection between the right terminals of components 3 and 5. The third circuit shows a connection between the left terminals of components 3 and 5.

The third type of connection is a connection to the battery. The POSITIVE battery terminal must be connected to the LEFT terminal of one of the components. This is shown in red for each of the circuits in the diagram. The negative battery terminal can be connected to any left or right terminal of one of the components. This is shown in green.

When all connections are made it should be possible to trace a single route, which goes through all components, from the positive battery terminal to the negative battery terminal.

In this problem you will be given the number of components (N) and are asked to find the number of different ways in which they can be connected. Each of these must use only the types of connection described above. Two circuits are regarded as different if the order of the components (following the route from positive to negative) is different. Because the number of circuits rises rapidly with N, you are asked to give the answer modulo 1000000007 (10^9 +7). The value of N will not be greater than 100000.

For N = 5 there are 8 different circuits. These are shown in the diagram. The order of the components in each of these circuits (in moving from the positive terminal to the negative terminal) is given in the list below.

1 2 3 4 5
1 2 3 5 4
1 2 4 3 5
1 3 2 4 5
4 5 3 2 1
4 5 3 1 2
4 2 1 3 5
5 3 1 2 4

Input/Output description: The first line of the input data will consist of a single integer P, the number of problems. P lines will follow. Each of these lines contains a single integer N for the number of components. Find the number of different circuits which can be achieved by following the connection rules above. Answers must be given modulo 1000000007 (10^9 +7). Combine all answers into a single string, separated by spaces.

Example:

input:
6
5
7
23
49
220
518

answer:
8 18 8727 180777656 564825489 873073059