For a given prime number p find all the number of pairs (m, n) of positive integers such that 1 ≤ m , n ≤ p(p-1)* and p divides nm - mn. Output the result modulo 1000000007.

INPUT

The first line contains a single positive integer T ≤ 100, the number of test cases. T test cases follow. The only line of each test case contains a prime number p , where 2 ≤ p ≤ 10^12.

OUTPUT

For each test case, output a single line containing the answer for the corresponding test case.

SAMPLE INPUT
1
3

SAMPLE OUTPUT
14

Explanation

Required pairs are (1, 1), (1, 4), (2, 2), (2, 4), (3, 3), (3, 6), (4, 1), (4, 2), (4, 4), (4, 5), (5, 4), (5, 5), (6, 3) and (6, 6).

见题面

见题面