Алгебраїчна робота команди#7695

Алгебраїчна робота команди

1 секунда

128 мегабайтів

Середня

Знамениті піонери теорії груп і лінійної алгебри вирішили об'єднати свої зусилля та скооперувати свої теорії. У теорії груп перестановки (також відомі як бієктивні функції) відіграють важливу роль. Для скінченної множини $A$ функція $σ : A \to A$ \sigma : A \rightarrow A називається перестановкою $A$ тоді й тільки тоді, коли існує функція $ρ : A \to A$ \rho : A \rightarrow A така, що

σ (ρ (a)) = a і ρ (σ (a)) = a для всіх a \in A

\sigma(\rho(a)) = a \text{ і } \rho(\sigma(a)) = a \text{ для всіх } a \in A

Інша частина нової команди — експерти з лінійної алгебри — працюють з ідемпотентними функціями. Такі функції, зокрема, з’являються як проєкції при обчисленні тіней у 3D-іграх або як транзитивне замикання. Функція $p : A \to A$ p : A \rightarrow A називається ідемпотентною тоді й тільки тоді, коли

p (p (a)) = p (a) для всіх a \in A

p(p(a)) = p(a) \text{ для всіх } a \in A

Для продовження своїх досліджень їм потрібна ваша допомога. Команду цікавлять неідемпотентні перестановки для заданої скінченної множини $A$ . Вони з’ясували, що результат залежить лише від розміру множини. Для заданого розміру $n$ ( $1 \leq n \leq 1 0^{5}$ 1 \leq n \leq 10^5) вам потрібно знайти кількість неідемпотентних перестановок множини розміру $n$ .

Вхідні дані

Спочатку вводиться ціле число $t$ ( $1 \leq t \leq 100$ 1 \leq t \leq 100), кількість тестів. Далі йде $t$ рядків, кожен з яких містить ціле число $n$ ( $1 \leq n \leq 1 0^{5}$ 1 \leq n \leq 10^5) — розмір множини.

Вихідні дані

Для кожного тесту виведіть у окремому рядку кількість неідемпотентних перестановок множини розміру $n$ за модулем $1000000007$ $= 1 0^{9} + 7$ = 10^9 + 7.

Приклади

Приклад 1