Many thanks for this problem to Clive Fraser!
More houses need to be built in the local town. The planning committee identified a strip of land on which they could built a long line of houses. The strip of land was divided into a number of adjacent plots of equal size. The size of a plot was sufficient for a single house but there would not be any space left over to create a garden. The planners decided that houses would be confined to the designated plots. So a house would not be able to extend into adjacent plots. However, the planners intended that some of the plots would be used as gardens or for communal spaces.
The planners initially invited architects to suggest how the line of plots should be used. All that was
required at this stage was to indicate which plots were to be used for houses and which plots would be left
for other uses. The planners received a large number of suggested layouts and had to choose between these.
After an initial inspection of the various layouts they decided to begin by rejecting all layouts where any
house was immediately adjacent to other houses on both sides. For example, if the strip of land consists of
only 5 plots then the arrangements HHGHH and HGHGH would both be acceptable. Here H represents a house and
G represents a garden or other communal space. In the first arrangement each house is adjacent to just one
other house. In the second arrangement each house has no immediate neighbours. Clearly there are other
acceptable arrangements. Conversely the arrangement GHHHG would be rejected because the central house has
immediate neighbours on both sides.
If we continue with this example, where the number of plots is 5, we can soon determine that there are 8
different arrangements that would be rejected. These are:
GGHHH
GHHHG
GHHHH
HGHHH
HHHGG
HHHGH
HHHHG
HHHHH
The actual number of plots in the strip is actually much larger than the 5 in this example. For the given
number of plots you need to find the number of different arrangements of houses which will be rejected by the
planners. This number can be very large so all answers are to be given modulo 1000000007 (10^9 +7).
Input/Output description: The first line of the input data will contain a single integer N, the number of
puzzles to solve. N lines will follow. Each line contains a single integer, giving the number of plots
available. For each number of plots find the number of house arrangements which will be rejected by the
planners (modulo 1000000007). Give all answers on a single line, separated by spaces.
Example:
input:
4
5
13
397
2954
answer:
8 5056 979120014 375262229