WoW CaLcuLaTIoN

Author: Abu Rayhan Ahmad

Leeana  Loves To Find Summation Of Any Series. Today Her Uncle Gave Her A Task:


F(1)=1

F(n)=(n*(26*n+3))+(7*n)-((n+1)*5)-(5*n) Where, N>1

 

Find The Answer Of F(1)+F(2)+….F(n). Sum Of All Upto F(n) Will Be Huge So You Have To Module The Answer With 1000000007.

She Knows That Your A Great Programmer. Can You Help Her.

Input Format

First line of input will consist of an integer T (T<=10^5), indicates the number of test cases

follow. Then there will be T lines, where each line contains a number N (1<=N<=10^9).

Output Format

Print the answer of this problem with module 1000000007.

Samples

Input
2 2 3
Output
100 329

Explanation:

for case 1:

f(1)=1

f(2)=99

so f(1)+f(2)=100

same as for case 2.

Limits
Language Time Memory
GNU C 11 2s 1024MB
GNU C++ 14 2s 1024MB
GNU C++ 11 1s 512MB
Statistics
Login To Submit