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} \)