
148  The 14th Zhejiang Provincial Collegiate Programming Contest Sponsored by TuSimple  L
Chiaki is interested in an infinite sequence a_{1}, a_{2}, a_{3}, ..., which defined as follows: where r_{n} is the smallest positive integer not in the set S_{n} = {a_{j}  a_{i}  1 ≤ i < j ≤ n}. 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 (10^{9} + 7). InputThere are multiple test cases. The first line of input contains an integer T (1 ≤ T ≤ 1000), indicating the number of test cases. For each test case: The first line contains an integer n (1 ≤ n < 10^{100}) without leading zeros. OutputFor each test case, output an integer denoting the answer. Sample Input11 1 2 3 4 5 6 7 8 9 10 1000000000 Sample Output1 3 7 15 31 52 94 145 247 359 834069170 