Sleeping goats tend to cause less mischief than when they are awake.
Gavin is a farmer who keeps a large herd of N goats, which are a constant
source of nuisance for Gavin. Recently the goats have unable to sleep, bleating
loudly throughout the night. After many sleepless nights of his own, Gavin
purchases N blankets so that each goat has something soft to sleep on. On that
next night all the goats sleep quietly (and therefore so does Gavin), and in
the morning after the goats have been driven out to the pasture to graze,
Gavin gathers up the blankets and washes them.
However when he redistributes the blankets back to the goats for the next night, Gavin notices something surprising - a goat will get very upset when given the same blanket for two nights in a row! Each goat is only able to sleep if given a different blanket than they were given the previous night.
Assuming that Gavin kept track of which blanket was given to which goat the previous night, how many different ways can Gavin distribute the blankets on this night?
Problem Statement
Input Data
First line is Q, the quantity of testcases.
Q lines will follow, each containing a single integer N.
Answer
Should contain N space-separated integers corresponding to the number of
ways Gavin could distribute N blankets among N goats such that no goat
receives the same blanket as the previous night.
Return all answers modulo 1000000007.
Example
input data:
3
2
5
10
answer:
1 44 1334961