You are given an integer $n$. Determine the value of the following expression:

$\sum_{s=0}^{n}\sum_{r=s}^{n}\binom nr\binom rs s^2$

Here, $\binom nk$ denotes the number of ways to choose $k$ objects from a set of $n$ objects.

Since the value of the expression can be large enough, output it modulo $10^9 + 7$.

Input format

• The first line contains a single integer $T$ denoting the number of test cases.
• Each of the next $T$ lines contains a single integer $n$.

Output format

The output should contain $T$ lines each containing the value of the expression for the respective integer $n$.

Constraints

$1\le T\le 10^6\\ 1\le n\le 10^{15}$