Chiaki is interested in an infinite sequence a1, a2, a3, ..., which defined as follows: Chiaki would like to know the sum of the first n terms of the sequence, i.e. . As this number may be very large, Chiaki is only interested in its remainder modulo (109 + 7).

输入描述:

There are multiple test cases. The first line of input contains an integer T (1 ≤ T ≤ 105), indicating the number of test cases. For each test case:The first line contains an integer n (1 ≤ n ≤ 1018).

输出描述:

For each test case, output an integer denoting the answer.