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 .