Зменшіть до одного

Розглянемо список цілих чисел $L$. Спочатку $L$ містить цілі числа від $1$ до $n$, кожне рівно один раз (але може містити кілька копій деяких цілих чисел). Порядок елементів у $L$ не важливий. Вам слід виконати наступну операцію $n-1$ разів:

• Виберіть два елементи зі списку, нехай це будуть $x$ та $y$. Вони можуть бути рівними.

• Видаліть вибрані елементи з $L$.

• Додайте число $x+y+x\cdot y$ у $L$.

В кінці $L$ містить одне ціле число. Знайдіть максимальне значення цього цілого числа. Оскільки відповідь може бути великою, обчисліть її за модулем $10^9+7$.

Вхідні дані

Перший рядок містить кількість тестів $t$. Кожен із наступних $t$ рядків містить одне ціле число $n(1\le n\le 10^6)$.

Вихідні дані

Для кожного тесту виведіть одне ціле чило — максимальне можливе значення останнього числа у списку, обчислене за модулем $10^9+7$.

Приклади