You will be given Q queries.
For each Query you have to find the sum of first N terms of the following series.
1 + 8.4 + 15.42 + 22.43 + ...
Input :
First line contains the number of queries.
In each query , there is one number N .
Output :
Print a single integer — the sum of first N terms of the above series. Since the answer can be large , print the sum % 109+7 , where % is the modulo operation .
Constraints :
1 <= Q <= 106
1 <= N <= 1018