Problem Description

You may not know this but it's a fact that Xinghai Square is Asia's largest city square. It is located in Dalian and, of course, a landmark of the city. It's an ideal place for outing any time of the year. And now:
  
  There are $ N $ children from a nearby primary school flying kites with a teacher. When they have a rest at noon, part of them (maybe none) sit around the circle flower beds. The angle between any two of them relative to the center of the circle is always a multiple of $\dfrac{2\pi}{N}$ but always not $\dfrac{2\pi}{N}$.
  
  Now, the teacher raises a question: How many different ways there are to arrange students sitting around the flower beds according to the rule stated above. To simplify the problem, every student is seen as the same. And to make the answer looks not so great, the teacher adds another specification: two ways are considered the same if they coincide after rotating.

Input

There are $ T $ tests ($ T\le50 $). Each test contains one integer $ N $. $ 1\le N\le1000000000\ (10^9) $. Process till the end of input.

Output

For each test, output the answer mod 1000000007 ($10^9+7$) in one line.

4
7
10

3
5
15