Harmonious Set

For a giving integer n ( n > 0 ) , the set Sn consists of the non negative integers less than n. For example:S5 = {0,1,2,3,4}. A subset of Sn is harmonious if and only if the sum of its elements is a multiply of n. Now your task is easy. For a given n , you should find the number of harmonious subset of Sn.

There is a number C in the first line , meaning there are C cases . C is guaranteed no more than 300.

Then C cases below. Each case is a positive integer n in a single line. n is not greater than 10^9.

For each case , Output the answer mod 1000000007 in a single line .

5
1
2
3
10
1000

2
2
4
104
618918635

2011 Multi-University Training Contest 13 - Host by HIT