Розглянемо список цілих чисел $L$. Спочатку $L$ містить цілі числа від $1$ до $n$, кожне рівно один раз (але може містити кілька копій деяких цілих чисел). Порядок елементів у $L$ не важливий. Вам слід виконати наступну операцію $n - 1$ разів: \begin{itemize} \item Виберіть два елементи зі списку, нехай це будуть $x$ та $y$. Вони можуть бути рівними. \item Видаліть вибрані елементи з $L$. \item Додайте число $x + y + x \cdot y$ у $L$. \end{itemize} В кінці $L$ містить одне ціле число. Знайдіть максимальне значення цього цілого числа. Оскільки відповідь може бути великою, обчисліть її за модулем $10^9 + 7$. \InputFile Перший рядок містить кількість тестів $t$. Кожен із наступних $t$ рядків містить одне ціле число $n~(1 \le n \le 10^6)$. \OutputFile Для кожного тесту виведіть одне ціле чило --- максимальне можливе значення останнього числа у списку, обчислене за модулем $10^9 + 7$.