Jack loves number series. One day he found a series

$1, 4, 11, 24, 45, 76, 119 ...$

ans wants to find the sum of first $n$ terms.

Since he got stuck in finding the sum so he wants your help.

Help him to find the sum of first $n$ terms.

Since the sum may be large so take modulo with $10^9+7$

Input

First line contain number of test cases $t$.

Next $t$ lines contains a number $n$.

Output

Print a single number denoting the sum of first n terms $modulo 10^9+7$

Constraints

$1 <= t <= 10^5$

$1 <= n <= 10^6$