ACM-ICPC Indonesia National Contest 2010

Problem E

Playing with Boxes

Time Limit: 3s

You may be don't know about this, but Ceemot does like to play with boxes during her free time. She has N different boxes in one pile. First, she splits them into two piles (not necessary the same size), then she picks one of the piles with at least two boxes and splits it into two again. She repeats this until each pile has only one box.

As a computer scientist, she wonders the number of different ways in which she can do this.

For example, if she begins with a pile of 3 boxes (A, B and C) then there are three ways to do her weird hobby:

  1. Split ABC into A and BC, split BC into B and C.
  2. Split ABC into B and AC, split AC into A and C.
  3. Split ABC into C and AB, split AB into A and B.

If she begins with a pile of 4 boxes (A, B, C and D) then there are eighteen ways to do this:

Help her to count the number of different ways in which she can carry out this splitting procedure. As the number may be very big, modulo the output with 1,000,000,007.


Input

The first line of input contains an integer T (1 ≤ T ≤ 1,000) the number of cases. Each case begins with an integer N (2 ≤ N ≤ 100,000) the number of different boxes Ceemot has in one pile originally.

Output

For each test case, output in a line the number of different ways in which she can carry out her splitting procedure. Modulo this number with 1,000,000,007.



Sample InputOutput for Sample Input
3
3
4
7
3
18
56700