Алгебраїчна робота команди
Знамениті піонери теорії груп і лінійної алгебри вирішили об'єднати свої зусилля та скооперувати свої теорії. У теорії груп перестановки, відомі також як бієктивні функції, відіграють важливу роль. Для скінченної множини A, функція σ : A → A називається перестановкою A, якщо існує така функція ρ : A → A, що
σ(ρ(a)) = a і ρ(σ(a)) = a для всіх a з A.
Інша частина нової команди — експерти з лінійної алгебри — працюють з ідемпотентними функціями. Вони використовуються, наприклад, при обчисленні тіней у 3D-іграх або при знаходженні транзитивних замикань. Функція p : A → A називається ідемпотентною, якщо
ρ(ρ(a)) = ρ(a) для всіх a з A.
Для продовження своїх досліджень їм потрібна ваша допомога. Команду цікавлять неідемпотентні перестановки для заданої скінченної множини A. Вони виявили, що результат залежить від розміру множини. Для заданого розміру n (1 ≤ n ≤ 10^5) вам потрібно знайти кількість неідемпотентних перестановок для множини розміру n.
Вхідні дані
Спочатку вводиться кількість тестів t (t ≤ 100). Далі йдуть t рядків, кожен з яких містить розмір множини n (1 ≤ n ≤ 10^5).
Вихідні дані
Для кожного тесту виведіть в окремому рядку кількість неідемпотентних функцій потужності n за модулем 1 000 000 007 = (10^9 + 7).