SP13523 GUMATH2 - Card Meets (medium)

Guardian is very weak at maths but still to compete in a certain exam he has to get good grades in mathematics this time. In the first class of the semester the Prof. asked students to find the number of ways deck (having N cards) could be shuffled that exactly one card is at the same position as before, and the students who successfully do this will be awarded with good marks in mid terms. Help Guardian solve this problem.

The input begins with the number T of test cases in a single line. In each of the next T lines there are one integer N.

For each test case you have to output on a single line the number of ways possible meeting the Prof.'s requirements. As the answer can be a huge number, simply output it modulo 10000009.