Lucru mare-i omenia

"În viață câștigi sau pierzi
Omenia s-o păstrezi, măi"

A trader keeps a daily log of trading results. Each day is recorded as either a winning day (W) or a losing day (L). Over a period of $2N$ trading days, the trader records exactly $N$ winning days and $N$ losing days.

A winning streak is any non-empty contiguous subsequence of days such that every day in that interval is a win (W). Two streaks are considered different if they correspond to different intervals.

Task

Compute the total sum of winning streaks over all valid sequences, modulo $10^9 + 7$.

Formally, let $\mathcal{A}$ be the set of all sequences of length $2N$ containing exactly $N$ characters W and $N$ characters L. Then the answer is:

where

Input data

The first line of the input contains a single integer $T$, representing the number of queries.

Each of the next $T$ lines contains a single integer $N$.

Output data

For each query, output a single line containing the answer corresponding to that value of $N$, modulo $10^9 + 7$.

Constraints and clarifications

• $1 \leq T \leq 10^5$
• $1 \leq N \leq 10^6$

Example

stdin

2
1
2

stdout

2
15

Explanation

For $N = 1$, the possible sequences are:

• WL $\rightarrow 1$ streak
• LW $\rightarrow 1$ streak

Total: $2$

For $N = 2$, all sequences and their number of winning streaks:

• WWLL $\rightarrow 3$
• WLWL $\rightarrow 2$
• WLLW $\rightarrow 2$
• LWWL $\rightarrow 3$
• LWLW $\rightarrow 2$
• LLWW $\rightarrow 3$

Total: $15$